Statistics

Problem Statement for "PowerOfInteger"

Problem Statement

A number y is said to be the k-th power of a number x if y = x^k, i.e., y is the product of k copies of x.

You are given two Strings left and right. Return the greatest k such that there is an integer y (left <= y <= right) such that y is the k-th power of some integer x.

Definition

Class:
PowerOfInteger
Method:
greatestPower
Parameters:
String, String
Returns:
int
Method signature:
int greatestPower(String left, String right)
(be sure your method is public)

Constraints

  • left will be an integer between 2 and 10^12, inclusive, without extra leading zeroes.
  • right will be an integer between left and 10^12, inclusive, without extra leading zeroes.

Examples

  1. "5"

    "20"

    Returns: 4

    The greatest power between 5 and 20 is 16=2^4.

  2. "10"

    "12"

    Returns: 1

    No nontrivial power of integer between 10 and 12, so return 1.

  3. "2"

    "100"

    Returns: 6

  4. "1000000000000"

    "1000000000000"

    Returns: 12

  5. "549755813888"

    "549755813888"

    Returns: 39

  6. "2"

    "1000000000000"

    Returns: 39

  7. "100"

    "101"

    Returns: 2

  8. "64"

    "100"

    Returns: 6

  9. "50"

    "64"

    Returns: 6

  10. "847288609443"

    "847288609443"

    Returns: 25

  11. "847288600000"

    "847288610000"

    Returns: 25

  12. "999869446364"

    "1000000000000"

    Returns: 12

  13. "999687621521"

    "1000000000000"

    Returns: 12

  14. "999687873092"

    "1000000000000"

    Returns: 12

  15. "995331951492"

    "996641179974"

    Returns: 5

  16. "999214379782"

    "1000000000000"

    Returns: 12

  17. "897219924734"

    "898088830625"

    Returns: 7

  18. "852709768329"

    "853678652515"

    Returns: 8

  19. "793318700304"

    "794491963389"

    Returns: 9

  20. "575882709250"

    "577500611776"

    Returns: 10

  21. "742499081092"

    "743349380865"

    Returns: 11

  22. "999035477086"

    "1000000000000"

    Returns: 12

  23. "549552029402"

    "550011441891"

    Returns: 39

  24. "677721463203"

    "679063326812"

    Returns: 14

  25. "469646896892"

    "470224585499"

    Returns: 15

  26. "152493545994"

    "153445072747"

    Returns: 16

  27. "762457797586"

    "763823806351"

    Returns: 17

  28. "67892099282"

    "69310517661"

    Returns: 36

  29. "274218239917"

    "275240506462"

    Returns: 38

  30. "3014328386"

    "4296244642"

    Returns: 32

  31. "9714457553"

    "10482061449"

    Returns: 21

  32. "31336344837"

    "32290749663"

    Returns: 22

  33. "93775780317"

    "94237386823"

    Returns: 23

  34. "282217733688"

    "283072551509"

    Returns: 24

  35. "846474621970"

    "847621457947"

    Returns: 25

  36. "2"

    "828634631"

    Returns: 29

  37. "2"

    "636193841"

    Returns: 29

  38. "2"

    "361966080"

    Returns: 28

  39. "2"

    "1016490012"

    Returns: 29

  40. "397402337"

    "1649569345"

    Returns: 30

  41. "2073478186"

    "3072790623"

    Returns: 31

  42. "3595552310"

    "5107698095"

    Returns: 32

  43. "8247700960"

    "8875942877"

    Returns: 33

  44. "16304829172"

    "17279341006"

    Returns: 34

  45. "33752143483"

    "34899397216"

    Returns: 35

  46. "68240188803"

    "69327753975"

    Returns: 36

  47. "136733169726"

    "138097519202"

    Returns: 37

  48. "274049615188"

    "274965810232"

    Returns: 38

  49. "549519160329"

    "550338260344"

    Returns: 39

  50. "2"

    "555181487"

    Returns: 29

  51. "2"

    "1036713238"

    Returns: 29

  52. "2"

    "554577732"

    Returns: 29

  53. "2"

    "390553755"

    Returns: 28

  54. "2"

    "236652708"

    Returns: 27

  55. "2"

    "1678152902"

    Returns: 30

  56. "2"

    "787615330"

    Returns: 29

  57. "2"

    "211917320"

    Returns: 27

  58. "2"

    "1850222175"

    Returns: 30

  59. "2"

    "341012225"

    Returns: 28

  60. "2"

    "148462507"

    Returns: 27

  61. "2"

    "255636195"

    Returns: 27

  62. "2"

    "1840270347"

    Returns: 30

  63. "2"

    "39633691"

    Returns: 25

  64. "2"

    "857247658"

    Returns: 29

  65. "2"

    "1884484298"

    Returns: 30

  66. "2"

    "1591303069"

    Returns: 30

  67. "2"

    "363123806"

    Returns: 28

  68. "2"

    "1810508817"

    Returns: 30

  69. "2"

    "23805398"

    Returns: 24

  70. "2"

    "913884358"

    Returns: 29

  71. "2"

    "1102596604"

    Returns: 30

  72. "2"

    "1659792244"

    Returns: 30

  73. "2"

    "1366402936"

    Returns: 30

  74. "2"

    "1828634631"

    Returns: 30

  75. "2"

    "636193841"

    Returns: 29

  76. "2"

    "1361966080"

    Returns: 30

  77. "2"

    "1016490012"

    Returns: 29

  78. "2"

    "2649569345"

    Returns: 31

  79. "1073478186"

    "4072790623"

    Returns: 31

  80. "3595552310"

    "6107698095"

    Returns: 32

  81. "8247700960"

    "9875942877"

    Returns: 33

  82. "15304829172"

    "18279341006"

    Returns: 34

  83. "32752143483"

    "35899397216"

    Returns: 35

  84. "68240188803"

    "70327753975"

    Returns: 36

  85. "136733169726"

    "138097519202"

    Returns: 37

  86. "274049615188"

    "274965810232"

    Returns: 38

  87. "548519160329"

    "550338260344"

    Returns: 39

  88. "492696344816"

    "971255932362"

    Returns: 39

  89. "523200785086"

    "597133982968"

    Returns: 39

  90. "336246550383"

    "366670042599"

    Returns: 6

  91. "932910685100"

    "968595573132"

    Returns: 6

  92. "46530676084"

    "976758951622"

    Returns: 39

  93. "464784099572"

    "697131618879"

    Returns: 39

  94. "262101965741"

    "912460657557"

    Returns: 39

  95. "927583781952"

    "978665655833"

    Returns: 6

  96. "220809334661"

    "551184282969"

    Returns: 39

  97. "496815045615"

    "965578450040"

    Returns: 39

  98. "348634383243"

    "824662244412"

    Returns: 39

  99. "505397978806"

    "823937362148"

    Returns: 39

  100. "95102648583"

    "856666681576"

    Returns: 39

  101. "97019291279"

    "561006183210"

    Returns: 39

  102. "33086584794"

    "595743632655"

    Returns: 39

  103. "172219770564"

    "201001814233"

    Returns: 9

  104. "463912736829"

    "607616049148"

    Returns: 39

  105. "301579234185"

    "740303741861"

    Returns: 39

  106. "170821396023"

    "822984009018"

    Returns: 39

  107. "734531120952"

    "780682513983"

    Returns: 17

  108. "148852289518"

    "675869822957"

    Returns: 39

  109. "335686102203"

    "580603939934"

    Returns: 39

  110. "292572174552"

    "746329956871"

    Returns: 39

  111. "638171624593"

    "692969777564"

    Returns: 14

  112. "175605393187"

    "830039046302"

    Returns: 39

  113. "329930977725"

    "743209376451"

    Returns: 39

  114. "90429557308"

    "750450565180"

    Returns: 39

  115. "247213894768"

    "895613653758"

    Returns: 39

  116. "432694844478"

    "721713289947"

    Returns: 39

  117. "330080413016"

    "390410361687"

    Returns: 8

  118. "45492478532"

    "107380973668"

    Returns: 36

  119. "331520676993"

    "453954891052"

    Returns: 8

  120. "130438970984"

    "974272979912"

    Returns: 39

  121. "137771019099"

    "924378353190"

    Returns: 39

  122. "379398238472"

    "925801773179"

    Returns: 39

  123. "182560882951"

    "300336029535"

    Returns: 38

  124. "305157960411"

    "957786897373"

    Returns: 39

  125. "46403881655"

    "391925741238"

    Returns: 38

  126. "1847994221"

    "759861923627"

    Returns: 39

  127. "276656420798"

    "921695719582"

    Returns: 39

  128. "1000000000000"

    "1000000000000"

    Returns: 12

  129. "1000000000000"

    "1000000000000"

    Returns: 12

  130. "1000000000000"

    "1000000000000"

    Returns: 12

  131. "996250626251"

    "996250626251"

    Returns: 5

  132. "1000000000000"

    "1000000000000"

    Returns: 12

  133. "897410677851"

    "897410677851"

    Returns: 7

  134. "852891037441"

    "852891037441"

    Returns: 8

  135. "794280046581"

    "794280046581"

    Returns: 9

  136. "576650390625"

    "576650390625"

    Returns: 10

  137. "743008370688"

    "743008370688"

    Returns: 11

  138. "1000000000000"

    "1000000000000"

    Returns: 12

  139. "549755813888"

    "549755813888"

    Returns: 39

  140. "678223072849"

    "678223072849"

    Returns: 14

  141. "470184984576"

    "470184984576"

    Returns: 15

  142. "152587890625"

    "152587890625"

    Returns: 16

  143. "762939453125"

    "762939453125"

    Returns: 17

  144. "68719476736"

    "68719476736"

    Returns: 36

  145. "274877906944"

    "274877906944"

    Returns: 38

  146. "3486784401"

    "3486784401"

    Returns: 20

  147. "10460353203"

    "10460353203"

    Returns: 21

  148. "31381059609"

    "31381059609"

    Returns: 22

  149. "94143178827"

    "94143178827"

    Returns: 23

  150. "282429536481"

    "282429536481"

    Returns: 24

  151. "847288609443"

    "847288609443"

    Returns: 25

  152. "67108864"

    "67108864"

    Returns: 26

  153. "134217728"

    "134217728"

    Returns: 27

  154. "268435456"

    "268435456"

    Returns: 28

  155. "536870912"

    "536870912"

    Returns: 29

  156. "1073741824"

    "1073741824"

    Returns: 30

  157. "2147483648"

    "2147483648"

    Returns: 31

  158. "4294967296"

    "4294967296"

    Returns: 32

  159. "8589934592"

    "8589934592"

    Returns: 33

  160. "17179869184"

    "17179869184"

    Returns: 34

  161. "34359738368"

    "34359738368"

    Returns: 35

  162. "68719476736"

    "68719476736"

    Returns: 36

  163. "137438953472"

    "137438953472"

    Returns: 37

  164. "274877906944"

    "274877906944"

    Returns: 38

  165. "549755813888"

    "549755813888"

    Returns: 39

  166. "732082482176"

    "732082482176"

    Returns: 5

    One that gives doubles a bit of difficulty

  167. "274794888224"

    "274794888224"

    Returns: 5

    Another hard case for doubles

  168. "706395741416"

    "706395741416"

    Returns: 3

    Another double trap, the other direction

  169. "960336273896"

    "960336273896"

    Returns: 3

  170. "999999999999"

    "999999999999"

    Returns: 1

  171. "999998000001"

    "999998000001"

    Returns: 2

  172. "100000000951"

    "100000000951"

    Returns: 1

  173. "1000000007"

    "1000000007"

    Returns: 1

  174. "549755813889"

    "847822609442"

    Returns: 25

  175. "100020001"

    "100020001"

    Returns: 2

  176. "847288609442"

    "847288609442"

    Returns: 1

  177. "2209"

    "2209"

    Returns: 2

  178. "4012009"

    "4012009"

    Returns: 2

  179. "2"

    "8"

    Returns: 3

  180. "1002001"

    "1002001"

    Returns: 2

  181. "12345678999"

    "12345678999"

    Returns: 1

  182. "999999999999"

    "1000000000000"

    Returns: 12

  183. "10201"

    "10201"

    Returns: 2

  184. "10000200001"

    "10000200001"

    Returns: 2

  185. "121066009"

    "121066009"

    Returns: 2

  186. "39601"

    "39601"

    Returns: 2

  187. "1234567891"

    "1234567891"

    Returns: 1

  188. "169"

    "169"

    Returns: 2

  189. "10000600009"

    "10000600009"

    Returns: 2

  190. "35"

    "37"

    Returns: 2

  191. "111111111111"

    "111111111111"

    Returns: 1

  192. "15241383936"

    "15241383936"

    Returns: 2

  193. "14278500637"

    "14278500637"

    Returns: 1

  194. "2"

    "999999999999"

    Returns: 39

  195. "778589170129"

    "778589170129"

    Returns: 2

  196. "999999999997"

    "999999999997"

    Returns: 1

  197. "99999999999"

    "99999999999"

    Returns: 1

  198. "45209390625"

    "45209390625"

    Returns: 2

  199. "4"

    "4"

    Returns: 2

  200. "100000000003"

    "100000000003"

    Returns: 1

  201. "121"

    "121"

    Returns: 2

  202. "2476097"

    "2476103"

    Returns: 5

  203. "252097800623"

    "252097800623"

    Returns: 1

  204. "274877906944"

    "549755813887"

    Returns: 38

  205. "549755813887"

    "549755813887"

    Returns: 1

  206. "999999999993"

    "999999999999"

    Returns: 1

  207. "194754273881"

    "194754273881"

    Returns: 7

  208. "32"

    "64"

    Returns: 6

  209. "275604541"

    "275604541"

    Returns: 1

  210. "1295"

    "1297"

    Returns: 4

  211. "2"

    "16"

    Returns: 4

  212. "16326961729"

    "16326961729"

    Returns: 2

  213. "87178291199"

    "87178291199"

    Returns: 1

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: