Problem Description

You are standing at position 0 on an infinite number line. On each move, you can go either left or right. During the n-th move (starting from 1), you take n steps. That is, your first move is 1 step, your second move is 2 steps, and so on.

Given an integer target, return the minimum number of moves required (starting from position 0) so that you reach the position target exactly.

• You may move left or right in each move.
• Each move must be of the next increasing length, starting from 1.
• You must reach target exactly, not pass or overshoot it.

Thought Process

At first glance, it seems like you could try every possible sequence of left and right moves, but the number of possibilities grows exponentially. Brute-forcing all combinations would be very slow for large targets.

Instead, let's look for patterns:

• Each move increases in size by 1, so after k moves, the total distance you could have covered (in one direction) is 1 + 2 + ... + k = k*(k+1)/2.
• But since you can choose to flip the direction of any move, you can "subtract" twice the sum of any subset of moves from your total distance.
• So the problem reduces to: Can you reach target by flipping the sign of some of the moves? That is, can you find a subset of moves whose sum is exactly the difference between the total distance and target, and this difference must be even (since flipping a move changes the total by an even number)?

Solution Approach

Here's how we can solve the problem efficiently:

1. Take the absolute value of target (since the problem is symmetric around 0).
2. Start with k = 0 and sum = 0.
3. Incrementally add k to sum (i.e., sum = 1, 3, 6, 10, ...).
4. Keep going until sum is at least as big as target and the difference sum - target is even (since flipping moves must change the sum by an even number).
5. Once both conditions are met, k is the answer.

Why does this work? Because flipping any move of size i changes your position by 2*i. So, you can only reach target if the "overshoot" (sum - target) is even and non-negative.

Example Walkthrough

Suppose target = 3.

1. First, take abs(3) = 3.
2. Start adding moves:
   • Move 1: sum = 1
   • Move 2: sum = 3 (sum >= target, sum - target = 0, which is even)
3. sum - target = 0 is even, so after 2 moves you can reach 3.
4. How? Move 1 right (+1), move 2 right (+2): 1 + 2 = 3.

Now, try target = 2:

• Move 1: sum = 1
• Move 2: sum = 3 (sum >= target, sum - target = 1, which is odd)
• Move 3: sum = 6 (sum - target = 4, which is even)

Time and Space Complexity

Brute-force: Would try all 2^k combinations for each k until reaching target. This is exponential time and not feasible for large targets.

Optimized approach (above):

• Each iteration increases k and sum. The loop runs at most O(sqrt(target)) times, because the sum grows quadratically with k.
• Space complexity is O(1), since only a few variables are used.

Summary

The key insight is that the sum of the first k moves can always reach any number less than or equal to that sum, as long as the overshoot is even (because you can flip moves). By incrementally increasing k and checking when the conditions are met, you find the minimum number of moves efficiently. This mathematical approach avoids brute-force and is both elegant and fast.

Code Implementation

class Solution:
    def reachNumber(self, target: int) -> int:
        target = abs(target)
        k = 0
        sum_ = 0
        while sum_ < target or (sum_ - target) % 2 != 0:
            k += 1
            sum_ += k
        return k
      

class Solution {
public:
    int reachNumber(int target) {
        target = abs(target);
        int k = 0;
        int sum = 0;
        while (sum < target || (sum - target) % 2 != 0) {
            ++k;
            sum += k;
        }
        return k;
    }
};
      

class Solution {
    public int reachNumber(int target) {
        target = Math.abs(target);
        int k = 0, sum = 0;
        while (sum < target || (sum - target) % 2 != 0) {
            k++;
            sum += k;
        }
        return k;
    }
}
      

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