Problem Description

You start at position 0 on an infinite number line and need to reach a target position.

You can make moves following these rules:

• Each move allows you to go either left or right
• On the 1st move, you take 1 step in your chosen direction
• On the 2nd move, you take 2 steps in your chosen direction
• On the 3rd move, you take 3 steps in your chosen direction
• And so on... on the i-th move, you take i steps

Your goal is to find the minimum number of moves needed to reach exactly the target position.

For example, if target = 2:

• Move 1: Go right 1 step (position = 1)
• Move 2: Go right 2 steps (position = 3)
• Move 3: Go left 3 steps (position = 0)
• Move 4: Go right 4 steps (position = 4)
• Move 5: Go left 5 steps (position = -1)
• Move 6: Go right 6 steps (position = 5)
• Move 7: Go left 7 steps (position = -2)
• Move 8: Go right 8 steps (position = 6)
• Move 9: Go left 9 steps (position = -3)
• Move 10: Go right 10 steps (position = 7)
• Move 11: Go left 11 steps (position = -4)

Actually, a better sequence would be:

• Move 1: Go right 1 step (position = 1)
• Move 2: Go left 2 steps (position = -1)
• Move 3: Go right 3 steps (position = 2)

So the answer would be 3 moves.

The solution leverages the fact that due to symmetry, we can work with the absolute value of the target. The key insight is that we keep moving in the positive direction (accumulating sum 1 + 2 + 3 + ... + k) until we either hit the target exactly or overshoot it. If we overshoot by an even amount, we can flip one of our previous moves from positive to negative to reach the target exactly. The move we flip would be the one with value equal to half the overshoot amount.

Intuition

Let's think about what happens when we make moves. If we always move in the positive direction, after k moves, we'd be at position 1 + 2 + 3 + ... + k = k*(k+1)/2.

Since we can move left or right at each step, we can think of each move as having a sign: positive for right, negative for left. So our final position is actually the sum of moves with their signs: ±1 ± 2 ± 3 ± ... ± k.

Here's the key observation: if we're at position s after always moving right, and s > target, then we've overshot by s - target. If this overshoot is even, we can reach the target exactly! How?

Consider that we made all positive moves to reach s. If we flip one of those moves from positive to negative, we lose twice that move's value from our sum. For example, if we flip move i from +i to -i, our sum decreases by 2i.

So if s - target = 2i for some move i we already made, we can flip that specific move to negative and reach the target exactly. This is why we need (s - target) % 2 == 0.

What if the overshoot is odd? Then we can't fix it by flipping any single existing move (since flipping changes the sum by an even amount). So we keep adding more moves until the overshoot becomes even.

This explains the algorithm: keep moving in the positive direction (adding 1, 2, 3, ...) until:

1. We reach or pass the target, AND
2. The overshoot (s - target) is even

When both conditions are met, the number of moves we've made is our answer. The actual sequence would involve flipping the appropriate move(s) to negative, but we don't need to track which ones - we just need to count the total moves.

Learn more about Math and Binary Search patterns.

Solution Approach

Based on our mathematical analysis, we implement the solution with a simple loop:

1. Handle symmetry: First, we take the absolute value of target since moving to position -5 requires the same number of steps as moving to position 5. We just need to mirror the moves.

2. Initialize variables:

   • s = 0: tracks our current position (sum of all moves so far)
   • k = 0: counts the number of moves we've made

3. Main loop: We continuously make moves in the positive direction:

   • Increment k by 1 (making the k-th move)
   • Add k to our position s (equivalent to moving right by k steps)
   • Check our stopping condition

4. Stopping condition: We stop when both conditions are met:

   • s >= target: We've reached or passed the target
   • (s - target) % 2 == 0: The overshoot is even

   When both are true, we return k as our answer.

The algorithm works because:

• If s == target, we've reached exactly where we want (overshoot is 0, which is even)
• If s > target with even overshoot, we can flip certain previous moves to negative. Specifically, we need to flip moves that sum to (s - target) / 2

For example, if target = 2:

• After move 1: s = 1, s < target, continue
• After move 2: s = 1 + 2 = 3, s > target, overshoot = 3 - 2 = 1 (odd), continue
• After move 3: s = 3 + 3 = 6, s > target, overshoot = 6 - 2 = 4 (even), stop

We return k = 3. The actual sequence would be +1 -2 +3 = 2 (we flipped move 2 since we needed to reduce our sum by 4, and flipping move 2 reduces it by 2 * 2 = 4).

The time complexity is O(sqrt(target)) since the sum 1 + 2 + ... + k grows quadratically, and space complexity is O(1).

Example Walkthrough

Let's walk through the solution for target = 5:

Step 1: Initialize

• Convert target to absolute value: target = |5| = 5
• Set s = 0 (current position), k = 0 (number of moves)

Step 2: Execute the main loop

Move 1:

• Increment k: k = 1
• Add to position: s = 0 + 1 = 1
• Check conditions: s < target (1 < 5), so continue

Move 2:

• Increment k: k = 2
• Add to position: s = 1 + 2 = 3
• Check conditions: s < target (3 < 5), so continue

Move 3:

• Increment k: k = 3
• Add to position: s = 3 + 3 = 6
• Check conditions:
  • s >= target ✓ (6 >= 5)
  • (s - target) % 2 = (6 - 5) % 2 = 1 % 2 = 1 (odd) ✗
• Overshoot is odd, so continue

Move 4:

• Increment k: k = 4
• Add to position: s = 6 + 4 = 10
• Check conditions:
  • s >= target ✓ (10 >= 5)
  • (s - target) % 2 = (10 - 5) % 2 = 5 % 2 = 1 (odd) ✗
• Overshoot is still odd, so continue

Move 5:

• Increment k: k = 5
• Add to position: s = 10 + 5 = 15
• Check conditions:
  • s >= target ✓ (15 >= 5)
  • (s - target) % 2 = (15 - 5) % 2 = 10 % 2 = 0 (even) ✓
• Both conditions met! Return k = 5

Step 3: Understanding the result

We need 5 moves to reach position 5. The overshoot was 10, meaning we need to flip moves that sum to 10 / 2 = 5. We can flip move 5 itself from positive to negative.

The actual sequence would be: +1 +2 +3 +4 -5 = 5

Verification: 1 + 2 + 3 + 4 - 5 = 10 - 5 = 5 ✓

Solution Implementation

Time and Space Complexity

Time Complexity: O(√|target|)

The algorithm increments k starting from 0 and accumulates the sum s = 1 + 2 + 3 + ... + k. The loop continues until s >= target and (s - target) % 2 == 0.

Since the sum of first k natural numbers is k(k+1)/2, we need to find the smallest k such that k(k+1)/2 >= |target|. Solving this inequality: k² + k - 2|target| >= 0, which gives us k ≈ √(2|target|) using the quadratic formula.

Even after reaching the target sum, we might need a few more iterations to satisfy the parity condition (s - target) % 2 == 0, but this adds at most a constant number of additional steps. Therefore, the number of iterations is proportional to √|target|.

Space Complexity: O(1)

The algorithm only uses a fixed number of variables (target, s, and k) regardless of the input size. No additional data structures or recursive calls are used, so the space complexity is constant.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Handle Negative Targets

One of the most common mistakes is not taking the absolute value of the target at the beginning. The problem allows negative targets, but due to symmetry, we should always work with positive values.

Incorrect approach:

def reachNumber(self, target: int) -> int:
    current_sum = 0
    step = 0
    # Missing abs(target) - will fail for negative targets
    while True:
        if current_sum >= target and (current_sum - target) % 2 == 0:
            return step
        step += 1
        current_sum += step

Solution: Always use target = abs(target) at the start.

2. Integer Overflow in Other Languages

While Python handles large integers gracefully, in languages like Java or C++, the sum calculation could overflow for very large targets.

Potential issue in C++/Java:

int current_sum = 0;  // Could overflow for large targets

Solution: Use long/long long data types or implement overflow checking:

long long current_sum = 0;

3. Misunderstanding the Stopping Condition

Some might think we need to stop as soon as current_sum >= target, missing the even difference requirement.

Incorrect logic:

while current_sum < target:  # Wrong! Misses the even difference check
    step += 1
    current_sum += step
return step

This would fail for cases like target = 2, where after 2 steps we have sum = 3 (overshoot by 1, which is odd).

Solution: Always check both conditions: current_sum >= target AND (current_sum - target) % 2 == 0

4. Off-by-One Error in Step Counting

Some implementations might incorrectly update the step counter, leading to off-by-one errors.

Incorrect ordering:

while True:
    current_sum += step  # Using step before incrementing it
    step += 1
    if current_sum >= target and (current_sum - target) % 2 == 0:
        return step  # Returns wrong value

Solution: Increment step first, then add to sum, or ensure you return the correct step count based on your implementation order.

5. Trying to Track Actual Moves

Attempting to maintain the actual sequence of moves (which steps go left/right) adds unnecessary complexity and memory usage.

Overcomplicated approach:

moves = []  # Unnecessary - we don't need to track actual moves
for i in range(1, n+1):
    if should_go_right(i):
        moves.append(('R', i))
    else:
        moves.append(('L', i))

Solution: Focus only on the mathematical property - we just need the count, not the actual sequence. The sequence can be reconstructed if needed by flipping appropriate moves.