Problem

You are standing at position 0 on an infinite number line. There is a destination at position target.

You can make some number of moves numMoves so that:

  • On each move, you can either go left or right.
  • During the ith move (starting from i == 1 to i == numMoves), you take i steps in the chosen direction.

Given the integer target, return _theminimum number of moves required (i.e., the minimum _numMoves ) to reach the destination.

Examples

Example 1

1
2
3
4
5
6

Input: target = 2
Output: 3
Explanation:
On the 1st move, we step from 0 to 1 (1 step).
On the 2nd move, we step from 1 to -1 (2 steps).
On the 3rd move, we step from -1 to 2 (3 steps).

Example 2

1
2
3
4
5

Input: target = 3
Output: 2
Explanation:
On the 1st move, we step from 0 to 1 (1 step).
On the 2nd move, we step from 1 to 3 (2 steps).

Constraints

  • -10^9 <= target <= 10^9
  • target != 0

Solution

Method 1 - Incremental Sum with Parity Check

Intuition

At each move, you can go left or right, and the step size increases by 1 each time. The sum of the first k natural numbers is k*(k+1)/2. We want to find the smallest k such that we can reach target (possibly by flipping the direction of some moves). The key is: if the sum overshoots the target, and the difference is even, we can flip some moves to reach exactly target.

Approach

  1. Take the absolute value of target (problem is symmetric).
  2. Incrementally add steps (1, 2, 3, …) until the sum >= target and (sum - target) is even.
  3. The answer is the number of steps taken.

Complexity

  • ⏰ Time complexity: O(sqrt(|target|)) – The smallest k with k(k+1)/2 >= |target| grows on the order of sqrt(|target|), and we loop until parity aligns.
  • 🧺 Space complexity: O(1) – Only a constant number of integer variables are used.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    int reachNumber(int target) {
        target = abs(target);
        int sum = 0, k = 0;
        while (sum < target || (sum - target) % 2 != 0) {
            ++k;
            sum += k;
        }
        return k;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

package solution

func reachNumber(target int) int {
    if target < 0 {
        target = -target
    }
    sum, k := 0, 0
    for sum < target || (sum-target)%2 != 0 {
        k++
        sum += k
    }
    return k
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public int reachNumber(int target) {
        target = Math.abs(target);
        int sum = 0, k = 0;
        while (sum < target || (sum - target) % 2 != 0) {
            ++k;
            sum += k;
        }
        return k;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun reachNumber(target: Int): Int {
        var t = kotlin.math.abs(target)
        var sum = 0
        var k = 0
        while (sum < t || (sum - t) % 2 != 0) {
            k++
            sum += k
        }
        return k
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def reachNumber(self, target: int) -> int:
        t = abs(target)
        sum_ = 0
        k = 0
        while sum_ < t or (sum_ - t) % 2 != 0:
            k += 1
            sum_ += k
        return k
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

impl Solution {
    pub fn reachNumber(target: i32) -> i32 {
        let mut t = target.abs();
        let mut sum = 0;
        let mut k = 0;
        while sum < t || (sum - t) % 2 != 0 {
            k += 1;
            sum += k;
        }
        k
    }
}
1
2
3
4
5
6
7
8
9

function reachNumber(target: number): number {
    target = Math.abs(target);
    let sum = 0, k = 0;
    while (sum < target || (sum - target) % 2 !== 0) {
        k++;
        sum += k;
    }
    return k;
}