Statistics

Problem Statement for "QuadraticJumping"

Problem Statement

You are on a straight line that is infinite in both directions. Your starting location is coordinate 0 and your goal is to reach coordinate goal using as few jumps as possible.

Your jumps are numbered starting from 1. The length of jump x must be exactly x^2 (x squared). For each jump you get to choose the direction in which you jump (left or right).

Return the smallest number of jumps needed to reach the given goal, or -1 if the goal cannot be reached.

Definition

Class:
QuadraticJumping
Method:
jump
Parameters:
long
Returns:
long
Method signature:
long jump(long goal)
(be sure your method is public)

Constraints

  • goal will be between 1 and 10^16, inclusive.

Examples

  1. 14

    Returns: 3

    Jump right three times: from 0 to 1, from 1 to 1+4 = 5, and from 5 to 5+9 = 14.

  2. 28

    Returns: 4

    Jump left, right, right, right: 0 to -1 to 3 to 12 to 28.

  3. 7

    Returns: 6

    Jump left, twice right, twice left, right: 0 to -1 to 3 to 12 to -4 to -29 to 7.

  4. 333383335000

    Returns: 10000

    Ten thousand jumps to the right.

  5. 1

    Returns: 1

  6. 2

    Returns: 4

  7. 10000000000000000

    Returns: 310723

  8. 3

    Returns: 2

  9. 4

    Returns: 3

  10. 5

    Returns: 2

  11. 6

    Returns: 3

  12. 7

    Returns: 6

  13. 8

    Returns: 7

  14. 9

    Returns: 6

  15. 10

    Returns: 4

  16. 20

    Returns: 4

  17. 26

    Returns: 7

  18. 30

    Returns: 4

  19. 36

    Returns: 7

  20. 46

    Returns: 8

  21. 85

    Returns: 9

  22. 87

    Returns: 9

  23. 107

    Returns: 9

  24. 110

    Returns: 11

  25. 118

    Returns: 11

  26. 120

    Returns: 7

  27. 127

    Returns: 9

  28. 130

    Returns: 7

  29. 136

    Returns: 8

  30. 143

    Returns: 9

  31. 151

    Returns: 10

  32. 161

    Returns: 9

  33. 166

    Returns: 11

  34. 177

    Returns: 9

  35. 188

    Returns: 11

  36. 228

    Returns: 11

  37. 4718

    Returns: 24

  38. 134879

    Returns: 74

  39. 593910

    Returns: 123

  40. 648687

    Returns: 125

  41. 926916

    Returns: 143

  42. 23146233

    Returns: 413

  43. 87625098

    Returns: 643

  44. 645789166

    Returns: 1247

  45. 47851485848

    Returns: 5236

  46. 60197865599

    Returns: 5653

  47. 71671788067

    Returns: 5993

  48. 318020693182

    Returns: 9844

  49. 350945058219

    Returns: 10173

  50. 357547063637

    Returns: 10237

  51. 711353864467

    Returns: 12877

  52. 1179055891094

    Returns: 15236

  53. 1932520668040

    Returns: 17964

  54. 3027629233969

    Returns: 20865

  55. 3385661650782

    Returns: 21659

  56. 6854314006592

    Returns: 27399

  57. 9958709817041

    Returns: 31030

  58. 10785516740821

    Returns: 31866

  59. 11286543227627

    Returns: 32353

  60. 13659923169527

    Returns: 34477

  61. 24880797026992

    Returns: 42104

  62. 30809391941040

    Returns: 45215

  63. 38539580474166

    Returns: 48716

  64. 39491890731803

    Returns: 49117

  65. 50753490775641

    Returns: 53398

  66. 57128013105956

    Returns: 55547

  67. 77913068063384

    Returns: 61600

  68. 95097976577835

    Returns: 65833

  69. 113042174376828

    Returns: 69735

  70. 135955472296735

    Returns: 74161

  71. 138195069419392

    Returns: 74567

  72. 152441659668676

    Returns: 77044

  73. 181442630693807

    Returns: 81649

  74. 228900300319554

    Returns: 88227

  75. 234518682170346

    Returns: 88940

  76. 326219547939600

    Returns: 99284

  77. 360325820707471

    Returns: 102630

  78. 385770271966458

    Returns: 104991

  79. 402394728277801

    Returns: 106477

  80. 495975894923702

    Returns: 114164

  81. 555687561107734

    Returns: 118575

  82. 587823185599896

    Returns: 120816

  83. 664167971649955

    Returns: 125837

  84. 783266352449731

    Returns: 132946

  85. 825522284323516

    Returns: 135296

  86. 864883213957814

    Returns: 137412

  87. 968970228933391

    Returns: 142718

  88. 1046839613248361

    Returns: 146445

  89. 1062053179260068

    Returns: 147151

  90. 1101395785739288

    Returns: 148944

  91. 1109981085046041

    Returns: 149330

  92. 1123077346316210

    Returns: 149915

  93. 1368240994967111

    Returns: 160113

  94. 1746533564826513

    Returns: 173686

  95. 1790979329232048

    Returns: 175147

  96. 2300205645845480

    Returns: 190384

  97. 2336678867586514

    Returns: 191384

  98. 2475410418360594

    Returns: 195100

  99. 2553953085477863

    Returns: 197141

  100. 2733964993407844

    Returns: 201668

  101. 3050082104514022

    Returns: 209160

  102. 3345696652104124

    Returns: 215711

  103. 3422352261057898

    Returns: 217347

  104. 3842473346086793

    Returns: 225897

  105. 4398288311348703

    Returns: 236305

  106. 4515685811534293

    Returns: 238389

  107. 4766719437270302

    Returns: 242727

  108. 5072807383198172

    Returns: 247812

  109. 5612516176125555

    Returns: 256306

  110. 5682306688371870

    Returns: 257367

  111. 5847080912148528

    Returns: 259831

  112. 6114275436883064

    Returns: 263728

  113. 6167357533749204

    Returns: 264488

  114. 6374459209651990

    Returns: 267416

  115. 6514635893303184

    Returns: 269363

  116. 7164317295546619

    Returns: 278037

  117. 7181492308513360

    Returns: 278256

  118. 7399133064593942

    Returns: 281039

  119. 7500294201036039

    Returns: 282314

  120. 7839716770187909

    Returns: 286510

  121. 8069306719758068

    Returns: 289283

  122. 8550628688510914

    Returns: 294923

  123. 8707531531262397

    Returns: 296714

  124. 8713431509446235

    Returns: 296782

  125. 9241173494333621

    Returns: 302657

  126. 6664213374266642

    Returns: 271408

  127. 333383334744

    Returns: 10003

  128. 9999999999999999

    Returns: 310725

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: