Description
You are standing at position 0 on an infinite number line. On each move, you can go left or right. During the n-th move, you take n steps. Return the minimum number of moves required to reach the destination target.
Examples
target = 23Right 1, left 2, right 3 → position 2.
target = 43Taking steps of 1, 2, and 3 reaches position 6, overshooting target 4 by 2. Negating step 1 (making it -1) gives -1+2+3=4. Three steps are needed.
target = -55Since the target is negative, the task requires go left overall. It is possible to achieve -5 by: Left 1 (pos -1), left 2 (pos -3), right 3 (pos 0), left 4 (pos -4), left 5 (pos -9). This overshoots, so trying: Left 1 (pos -1), left 2 (pos -3), left 3 (pos -6), right 4 (pos -2), right 5 (pos 3). Better approach: Right 1 (pos 1), left 2 (pos -1), left 3 (pos -4), left 4 (pos -8), right 5 (pos -3). Optimal: Left 1 (pos -1), left 2 (pos -3), left 3 (pos -6), right 4 (pos -2), left 5 (pos -7), giving us -5 in some combination within 5 moves.
Constraints
- •
-10^9 ≤ target ≤ 10^9 - •
target != 0