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
14
Returns: 3
Jump right three times: from 0 to 1, from 1 to 1+4 = 5, and from 5 to 5+9 = 14.28
Returns: 4
Jump left, right, right, right: 0 to -1 to 3 to 12 to 28.7
Returns: 6
Jump left, twice right, twice left, right: 0 to -1 to 3 to 12 to -4 to -29 to 7.333383335000
Returns: 10000
Ten thousand jumps to the right.