Statistics

Problem Statement for "ReverseAndIncrease"

Problem Statement

You have a display that shows a single positive integer in base 10. Initially, the value shown on the display is s. Your goal is to change that value to t.

You can change the value shown on the display by pressing buttons. There are two buttons attached to the display: a button labeled "increase" and a button labeled "reverse". Their effects are as follows:

  • Pressing the button "increase" increments the number shown on the display: if the current number is x, it changes to x+1.
  • The button "reverse" can only be pressed if the last digit of the current number is non-zero. Pressing this button reverses the digits of the number shown on the display. If the last digit of the current number is zero, this button is disabled.
You are given the longs s and t. Is there a sequence of zero or more button presses that changes s into t? Return "Possible" if such a sequence of actions exists, and "Impossible" if it does not exist.

Definition

Class:
ReverseAndIncrease
Method:
isPossible
Parameters:
long, long
Returns:
String
Method signature:
String isPossible(long s, long t)
(be sure your method is public)

Constraints

  • s will be between 1 and 1,000,000,000,000,000,000 (10^18), inclusive.
  • t will be between 1 and 1,000,000,000,000,000,000 (10^18), inclusive.

Examples

  1. 321

    125

    Returns: "Possible"

    One possible solution is to push the buttons in the order "reverse, increase, increase". The number will change as follows: 321 -> 123 -> 124 -> 125.

  2. 120

    21

    Returns: "Impossible"

    Note that we are not allowed to push the "reverse" button in this situation to change 120 into 021 = 21. In fact, we can easily prove that each number that can be obtained from 120 by pressing buttons will have at least three digits. Thus, producing 21 is impossible.

  3. 58

    58

    Returns: "Possible"

    This time we don't need to push any button.

  4. 1234567890123456

    123456

    Returns: "Impossible"

    Watch out for overflow.

  5. 123456

    1234567890123456

    Returns: "Possible"

  6. 5

    3

    Returns: "Impossible"

  7. 1

    3

    Returns: "Possible"

  8. 999

    998

    Returns: "Impossible"

  9. 998

    997

    Returns: "Possible"

  10. 104

    101

    Returns: "Impossible"

  11. 104

    99

    Returns: "Impossible"

  12. 102

    101

    Returns: "Impossible"

  13. 101

    100

    Returns: "Impossible"

  14. 999

    1000

    Returns: "Possible"

  15. 999

    999

    Returns: "Possible"

  16. 1000000000000000000

    1000000000000000000

    Returns: "Possible"

  17. 999999999999999999

    999999999999999999

    Returns: "Possible"

  18. 999999999999989999

    100000000000000002

    Returns: "Possible"

  19. 1001

    1002

    Returns: "Possible"

  20. 100000000000000001

    10002

    Returns: "Impossible"

  21. 1000002

    9999999999999999

    Returns: "Possible"

  22. 1000000000

    799371267598609

    Returns: "Possible"

  23. 100000000000000001

    100000000000000002

    Returns: "Possible"

  24. 3

    159247171061

    Returns: "Possible"

  25. 1000000000000000000

    100000000

    Returns: "Impossible"

  26. 10000000000000001

    26490

    Returns: "Impossible"

  27. 1000001

    1000001

    Returns: "Possible"

  28. 10000000001

    79071681007

    Returns: "Possible"

  29. 607

    100000000001

    Returns: "Possible"

  30. 10000000000000

    1

    Returns: "Impossible"

  31. 102

    787

    Returns: "Possible"

  32. 8252960243

    999999999999999

    Returns: "Possible"

  33. 1000001

    1000002

    Returns: "Possible"

  34. 100000000000000000

    100000000000000001

    Returns: "Possible"

  35. 18933173

    2

    Returns: "Impossible"

  36. 999999

    100000000000000002

    Returns: "Possible"

  37. 1000000001

    1000000000001

    Returns: "Possible"

  38. 100000000000002

    100000000000002

    Returns: "Possible"

  39. 10000000000000001

    10000000000000000

    Returns: "Impossible"

  40. 10000000

    2363310213831

    Returns: "Possible"

  41. 100000002

    999999

    Returns: "Impossible"

  42. 63757085505

    536138297877

    Returns: "Possible"

  43. 10000000001

    10000000001

    Returns: "Possible"

  44. 99999999999999

    100000000000001

    Returns: "Possible"

  45. 9999999

    10000000000000000

    Returns: "Possible"

  46. 804268502101424365

    765400817903933675

    Returns: "Possible"

  47. 1269265573

    708920374

    Returns: "Impossible"

  48. 9999999

    1000000000000001

    Returns: "Possible"

  49. 100002

    100002

    Returns: "Possible"

  50. 10001

    49813

    Returns: "Possible"

  51. 100

    10000000000

    Returns: "Possible"

  52. 47940757497669

    10000000000001

    Returns: "Impossible"

  53. 94738132922833461

    99999999999999999

    Returns: "Possible"

  54. 1000000000000000000

    1001

    Returns: "Impossible"

  55. 1000000000000000000

    1000000000000000000

    Returns: "Possible"

  56. 99999999999999999

    10001

    Returns: "Impossible"

  57. 365910458944825210

    4518963

    Returns: "Impossible"

  58. 1000000000002

    100000000002

    Returns: "Impossible"

  59. 10000

    10001

    Returns: "Possible"

  60. 100000000000001

    999999999999999

    Returns: "Possible"

  61. 1000000001

    9999

    Returns: "Impossible"

  62. 42407982921436

    10000000000002

    Returns: "Possible"

  63. 1

    9

    Returns: "Possible"

  64. 10000000001

    15321608295

    Returns: "Possible"

  65. 347132

    100002

    Returns: "Possible"

  66. 2

    2

    Returns: "Possible"

  67. 1

    99999999999

    Returns: "Possible"

  68. 3

    5

    Returns: "Possible"

  69. 100

    639

    Returns: "Possible"

  70. 100000000000000000

    9999999999999

    Returns: "Impossible"

  71. 338736064

    99999

    Returns: "Impossible"

  72. 1

    100000000000000

    Returns: "Possible"

  73. 99999

    9999999999999

    Returns: "Possible"

  74. 101

    442

    Returns: "Possible"

  75. 9999999999999999

    10000000000000002

    Returns: "Possible"

  76. 192

    100

    Returns: "Impossible"

  77. 10000000000000002

    1000002

    Returns: "Impossible"

  78. 3

    6

    Returns: "Possible"

  79. 1919

    638195

    Returns: "Possible"

  80. 7

    100000000000

    Returns: "Possible"

  81. 3

    10000000000000001

    Returns: "Possible"

  82. 10000000000000002

    995240420076491344

    Returns: "Possible"

  83. 3

    100002

    Returns: "Possible"

  84. 1000000000000000000

    1000000000000000000

    Returns: "Possible"

  85. 1000000000

    500657

    Returns: "Impossible"

  86. 29883824

    3527277

    Returns: "Impossible"

  87. 1000000000001

    100000002

    Returns: "Impossible"

  88. 10000002

    99999999

    Returns: "Possible"

  89. 1000000000000000000

    1000000000

    Returns: "Impossible"

  90. 9595

    9

    Returns: "Impossible"

  91. 231654

    100001

    Returns: "Impossible"

  92. 10000000000000001

    10000000000000002

    Returns: "Possible"

  93. 1000000000000000000

    1000000000000000000

    Returns: "Possible"

  94. 102

    946133226160859

    Returns: "Possible"

  95. 7

    1000000000000001

    Returns: "Possible"

  96. 999999999999

    100000000000000000

    Returns: "Possible"

  97. 426067870

    1000002

    Returns: "Impossible"

  98. 999999999999999999

    999

    Returns: "Impossible"

  99. 10000000000000002

    10000000

    Returns: "Impossible"

  100. 100000000000000001

    849

    Returns: "Impossible"

  101. 1000000000000

    68450

    Returns: "Impossible"

  102. 3

    10001

    Returns: "Possible"

  103. 1000000002

    1000000002

    Returns: "Possible"

  104. 100000000000000002

    100000000000000

    Returns: "Impossible"

  105. 1000000000000000000

    1000000000000000000

    Returns: "Possible"

  106. 9999999

    1000000

    Returns: "Impossible"

  107. 1000000000001

    100000000000001

    Returns: "Possible"

  108. 9999999

    1000001

    Returns: "Impossible"

  109. 100000000000000

    100000000000002

    Returns: "Possible"

  110. 1000000000002

    1000000000000

    Returns: "Impossible"

  111. 13912

    100000002

    Returns: "Possible"

  112. 1000

    8133

    Returns: "Possible"

  113. 100000000000002

    1000000000000000000

    Returns: "Possible"

  114. 10001

    1000000000000000

    Returns: "Possible"

  115. 100000000000000001

    100000000000000001

    Returns: "Possible"

  116. 99999

    100000000000000000

    Returns: "Possible"

  117. 1000000000000000000

    375719841401112944

    Returns: "Impossible"

  118. 3425

    1000

    Returns: "Impossible"

  119. 100000000000002

    1002

    Returns: "Impossible"

  120. 10000000000

    10000000002

    Returns: "Possible"

  121. 100000000002

    736385452538

    Returns: "Possible"

  122. 9999999999999999

    1000000000000001

    Returns: "Impossible"

  123. 99999999999999999

    10000000000000001

    Returns: "Impossible"

  124. 1000

    8954

    Returns: "Possible"

  125. 100000000002

    100000000000

    Returns: "Impossible"

  126. 1000000000000000000

    8142637871989

    Returns: "Impossible"

  127. 1002

    1000

    Returns: "Impossible"

  128. 10001

    34552091176409

    Returns: "Possible"

  129. 10000000000000000

    10000000000000001

    Returns: "Possible"

  130. 6

    8

    Returns: "Possible"

  131. 1

    3

    Returns: "Possible"

  132. 100000000001

    100000000001

    Returns: "Possible"

  133. 1001

    99999999999

    Returns: "Possible"

  134. 100000000000001

    999999999999999

    Returns: "Possible"

  135. 1000000000000000000

    1000000000000000000

    Returns: "Possible"

  136. 88954527689208

    88246821597121

    Returns: "Possible"

  137. 100000000000000002

    100000000000

    Returns: "Impossible"

  138. 999999999999999999

    1001

    Returns: "Impossible"

  139. 624322996532109562

    999999999999999

    Returns: "Impossible"

  140. 1000000000000000

    1000000000000002

    Returns: "Possible"

  141. 1000

    1002

    Returns: "Possible"

  142. 99999999

    10000000001

    Returns: "Possible"

  143. 3

    2

    Returns: "Impossible"

  144. 1001

    9999

    Returns: "Possible"

  145. 8

    3

    Returns: "Impossible"

  146. 7385775743099

    9999999999999

    Returns: "Possible"

  147. 9999999

    999999

    Returns: "Impossible"

  148. 3

    9

    Returns: "Possible"

  149. 75778

    10000

    Returns: "Impossible"

  150. 99999999999999999

    10000000000

    Returns: "Impossible"

  151. 99999999999999999

    5

    Returns: "Impossible"

  152. 300477915249934

    719368286978157

    Returns: "Possible"

  153. 1000001

    1000000

    Returns: "Impossible"

  154. 1755234

    99999

    Returns: "Impossible"

  155. 1

    9999999999999

    Returns: "Possible"

  156. 10000000000002

    10000000000002

    Returns: "Possible"

  157. 80087040

    532206628

    Returns: "Possible"

  158. 102

    244716018

    Returns: "Possible"

  159. 100000000000000001

    999999999999999999

    Returns: "Possible"

  160. 1000001

    9999

    Returns: "Impossible"

  161. 100000000000001

    100000000000001

    Returns: "Possible"

  162. 10000000

    570012916

    Returns: "Possible"

  163. 1000000000000000000

    100000000000

    Returns: "Impossible"

  164. 6

    1000000000000002

    Returns: "Possible"

  165. 100000000

    10000002

    Returns: "Impossible"

  166. 100002

    9999999

    Returns: "Possible"

  167. 1000000000000001

    10000001

    Returns: "Impossible"

  168. 100000000000001

    13204765400980

    Returns: "Impossible"

  169. 7

    7

    Returns: "Possible"

  170. 10001

    999999999999999999

    Returns: "Possible"

  171. 90051479295563060

    10000000000000002

    Returns: "Possible"

  172. 100000000

    99999999999999

    Returns: "Possible"

  173. 9

    3

    Returns: "Impossible"

  174. 1000002

    10000000000000002

    Returns: "Possible"

  175. 96652535265326606

    10000000000000002

    Returns: "Possible"

  176. 100000000001

    999999999999

    Returns: "Possible"

  177. 98525891160

    100000000000

    Returns: "Possible"

  178. 11640299

    10000000

    Returns: "Impossible"

  179. 100

    58387784637992

    Returns: "Possible"

  180. 9999999

    9999999

    Returns: "Possible"

  181. 10000000000000

    1000000000000000000

    Returns: "Possible"

  182. 5558810643

    100000000002

    Returns: "Possible"

  183. 22327

    10002

    Returns: "Possible"

  184. 1000

    9999

    Returns: "Possible"

  185. 100000

    999999

    Returns: "Possible"

  186. 100000000000000002

    895817

    Returns: "Impossible"

  187. 999999999999999999

    10000000000

    Returns: "Impossible"

  188. 1000000000000000

    100000001

    Returns: "Impossible"

  189. 2

    2

    Returns: "Possible"

  190. 10000000001

    10000000001

    Returns: "Possible"

  191. 99999999999999

    10000000000000

    Returns: "Impossible"

  192. 2177224082

    100000000000001

    Returns: "Possible"

  193. 797113130279

    1002

    Returns: "Impossible"

  194. 100000000000001

    100000000000002

    Returns: "Possible"

  195. 1000000000000002

    10000000001

    Returns: "Impossible"

  196. 100002

    1000000000002

    Returns: "Possible"

  197. 333208512910959274

    99999999

    Returns: "Impossible"

  198. 1000000002

    100000000000000000

    Returns: "Possible"

  199. 10000000002

    99999999999999

    Returns: "Possible"

  200. 67965911232

    20932294234

    Returns: "Possible"

  201. 79573625946963

    5727387956540140

    Returns: "Possible"

  202. 10000000000000000

    99999999999999999

    Returns: "Possible"

  203. 1000000000000

    1000000000001

    Returns: "Possible"

  204. 3

    10000000000000001

    Returns: "Possible"

  205. 1000000000

    99999999999

    Returns: "Possible"

  206. 99999999

    10000000

    Returns: "Impossible"

  207. 8

    100000000000000001

    Returns: "Possible"

  208. 100

    950

    Returns: "Possible"

  209. 1000000000002

    8950600224985

    Returns: "Possible"

  210. 152687639080

    100000000000

    Returns: "Impossible"

  211. 5

    1000000000000000000

    Returns: "Possible"

  212. 445

    999

    Returns: "Possible"

  213. 1000000001

    10000000000002

    Returns: "Possible"

  214. 100000000000002

    1000000

    Returns: "Impossible"

  215. 8

    5

    Returns: "Impossible"

  216. 100001

    100000

    Returns: "Impossible"

  217. 99999999999999

    10000000000001

    Returns: "Impossible"

  218. 10000000000

    1

    Returns: "Impossible"

  219. 5

    4

    Returns: "Impossible"

  220. 998

    102

    Returns: "Possible"

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: