You start at position 0 on an infinite number line. On the i th move, you must walk exactly i steps, and you may choose to move either left or right.
Given an integer target, return the minimum number of moves required to land exactly on position target.
Constraints:
Input: target = 1-int
Output: 1-int
Explanation: On move 1, walk 1 step to the right and land on position 1.
Input: target = -4-int
Output: 3-int
Explanation: Use 3 moves with step sizes 1, 2, 3. Going left 1, left 2, right 3 (0 → -1 → -3 → 0) doesn’t work, but right 1, left 2, left 3 (0 → +1 → -1 → -4) does. Thus 3 moves are enough, and 2 moves can only reach ±3 or ±1, not -4.
Input: target = 999999937-int
Output: 44721-int
Explanation: Let S = 1 + 2 + ... + n = n(n+1)/2. We need the smallest n such that S ≥ |target| and S - |target| is even (so some moves can be flipped to adjust by an even amount), and the smallest n satisfying this is 44721.
Input: target = -1000000000-int
Output: 44723-int
Explanation: Only the absolute value matters for the move count. The smallest n with S = n(n+1)/2 ≥ 1,000,000,000 is near 44721, but the parity condition (S - |target| must be even) is not met until n = 44723, so the answer is 44723.
Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem: