Domain 2MediumMEDIUM

Reach a Number

Calculate minimum moves to reach target by summing integers until parity matches.

Domain: medium•Updated: 2026-08-31
#Math#Greedy#O(sqrt(target))#O(1)

Problem Breakdown

We start at position 0 on an infinite number line and need to reach a specific integer target. The constraint is that the nn-th move must consist of exactly nn steps (move 1 = 1 step, move 2 = 2 steps, etc.). At each move, we can choose direction: left (-) or right (+).

Inputs:

  • target: An integer representing destination position. Range is [−109,109][-10^9, 10^9]. Constraints specify non-zero (though logic handles zero naturally if needed).

Outputs:

  • Minimum number of moves to reach exactly the target.

Implicit Constraints & Edge Cases:

  • Symmetry: The problem is symmetric around 0. Reaching -5 takes the same steps as reaching +5 because we can flip all directions at once. We will work with abs(target).
  • Overshoot Parity: Since step sizes are 1,2,…1, 2, \dots, simply summing them gives a maximum reach distance (Sn=n(n+1)/2S_n = n(n+1)/2). If this sum exceeds the target by an odd amount, we cannot correct it because flipping any previous move changes the total parity (difference) by an even number. We must overshoot until the difference is divisible by 2 and non-negative.
  • Overflow: While standard integers in languages like Java/C++ might overflow for very large sums without care, Python handles arbitrary precision automatically. The logic relies on mathematical properties rather than simulation of every position to avoid TLE (Time Limit Exceeded).

Intuition

A brute-force approach using BFS or DFS would explore all possible paths (2n2^n possibilities), which is exponential and infeasible for large targets like 10910^9. Even a simple greedy walk without parity checks might fail.

Key Insight: The maximum distance reachable after n moves is the sum of integers from 1 to n, denoted as sum_n. We need two conditions met:

  1. Reachability: The total steps taken (sum_n) must be at least equal to the absolute target value (∣target∣|target|). If we haven’t reached it yet, we simply continue moving forward (adding more moves) until we cover that distance.
  2. Parity Adjustment: Once sum_n ≥\ge ∣target∣|target|, let the difference be diff = sum_n - |target|. We need to flip some previous steps from positive (+) to negative (-). Flipping a step of size kk reduces the total distance by exactly 2×k2 \times k. Therefore, we can only reduce our overshoot amount if it is an even number.
    • If diff is odd, adding one more move (n+1n+1) changes both the sum and potentially the parity. We keep incrementing moves until sum_n - |target| becomes a non-negative even number.

Approach

  1. Normalize input: Convert target to its absolute value since direction doesn’t change step count logic.
  2. Initialize variables for current move index (n) and total distance covered (current_sum). Start at n=0n=0, sum=0.
  3. Loop while either of the following is true:
    • We haven’t reached or passed the target yet (current_sum < target).
    • The difference between our current position (max reach) and target is odd ((current_sum - target) % 2 != 0).
  4. Inside loop, increment n by 1 and add it to current_sum.
  5. Return the final value of n.

Complexity Analysis

  • Time Complexity: O(target)O(\sqrt{target}). The sum grows quadratically (≈n2/2\approx n^2/2). To reach a target magnitude TT, we need roughly 2⋅T\sqrt{2 \cdot T} steps. For 10910^9, this is approximately 45,000 iterations, which fits well within time limits (typically ~1 second for Python allows millions of operations).
  • Space Complexity: O(1)O(1). We only store a few integer variables regardless of input size.

Solution

def reachNumber(target: int) -> int:
    # Work with absolute value due to symmetry (left/right are equivalent in cost)
    target = abs(target)
    
    n = 0          # Current move number
    current_sum = 0
    
    while True:
        n += 1
        current_sum += n
        
        # Condition 1: We must have covered at least the distance to target.
        # Condition 2: The difference between sum and target must be even 
        # so we can flip signs of previous steps to correct parity.
        if (current_sum >= target) and ((current_sum - target) % 2 == 0):
            return n

# Example usage / Test cases
print(reachNumber(3))   # Output: 2
print(reachNumber(-2))  # Output: 3

Edge Cases Handled

  • Negative Target: Addressed by taking abs(target) immediately, treating -5 identically to +5.
  • Large Inputs (10910^9): The algorithm relies on arithmetic progression properties rather than simulation of every coordinate step, preventing overflow issues in fixed-width languages and ensuring efficiency within time limits for Python’s arbitrary precision integers.
  • Zero Difference: If target is 0 (though constraints say non-zero), the loop condition logic holds naturally as sum starts at 0; however, based on problem note, we assume target ≠\neq 0. The code handles it gracefully anyway by returning immediately if initialized correctly or via first iteration check.
  • Parity Mismatch: If current_sum - target is odd (e.g., overshoot of 1), the loop continues to increment nn. Adding an even number (2k2k) changes parity, adding an odd number flips it; eventually a valid state is found within at most +3 iterations after initial reach.