LeetCode 754 - Reach a Number

Difficulty: 🟡 Medium
Topics: Math, Binary Search

Solution

Problem Understanding

The problem asks us to find the minimum number of moves required to reach a specific position on an infinite number line starting from position 0. Each move i allows you to move exactly i steps, either to the left or the right. The input is a single integer target, which can be positive or negative, representing the position we must reach. The output is a single integer indicating the minimum number of moves.

The key constraints are that target can be very large, up to ±10^9, and it is never zero. This eliminates the trivial case of starting at the target. Edge cases include negative targets (which are symmetric with positive targets) and targets that require flipping directions to reach exactly.

The critical observation is that the sum of the first n natural numbers is n*(n+1)/2. The problem can be reframed as finding the smallest n such that this sum, possibly adjusted by flipping some moves, equals the absolute value of target. Negative targets are handled by symmetry: the solution is the same as for the positive value.

Approaches

A brute-force approach would try all possible sequences of left and right moves for increasing move counts until the target is reached. For each move count, it would generate all 2^n combinations of directions, compute the resulting position, and check if it matches the target. While correct, this approach is completely impractical because the number of combinations grows exponentially, especially given that the target can be as large as 10^9.

The optimal approach leverages a mathematical insight. Let t be the absolute value of target. We want the smallest n such that the sum 1 + 2 + ... + n is at least t and the difference (sum - t) is even. This is because flipping the direction of some moves changes the total sum by an even amount. Therefore, we iterate to find the first n where the cumulative sum is ≥ t and (sum - t) % 2 == 0.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Generates all sequences of moves and directions
Optimal	O(√target)	O(1)	Uses the sum of natural numbers and parity check to find minimum moves

Algorithm Walkthrough

Take the absolute value of target to simplify the problem, since moving left or right is symmetric.
Initialize sum to 0 and n to 0. These variables track the cumulative sum of moves and the current move number.
While sum is less than target or (sum - target) is odd, increment n and add it to sum. This ensures we have enough moves to reach target and that flipping moves can exactly hit the target if necessary.
Once the loop exits, n is the minimum number of moves required.
Return n.

Why it works: The sum of the first n moves increases with n. Once the sum exceeds target and the difference is even, flipping the direction of some moves will adjust the sum to exactly equal target. This guarantees correctness.

Python Solution

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

The implementation first converts target to its absolute value to handle symmetry. It then iteratively sums consecutive integers while checking if the sum has reached or exceeded the target and if the difference is even. Once these conditions are satisfied, the current move count n is returned as the answer.

Go Solution

func reachNumber(target int) int {
    if target < 0 {
        target = -target
    }
    n := 0
    total := 0
    for total < target || (total-target)%2 != 0 {
        n++
        total += n
    }
    return n
}

The Go implementation mirrors the Python version, using standard integer arithmetic. Negative targets are converted to positive, and a loop accumulates the sum while checking the parity condition.

Worked Examples

Example 1: target = 2

Step	n	total	total >= target?	(total - target) % 2 == 0?
1	1	1	No	-
2	2	3	Yes	(3-2)=1, odd
3	3	6	Yes	(6-2)=4, even

Minimum moves = 3

Example 2: target = 3

Step	n	total	total >= target?	(total - target) % 2 == 0?
1	1	1	No	-
2	2	3	Yes	(3-3)=0, even

Minimum moves = 2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(√target)	The sum of the first n natural numbers grows as n^2, so n ≈ √target iterations are sufficient
Space	O(1)	Only a few integer variables are used

The loop increments n and accumulates the sum until the conditions are met, which requires approximately √target iterations due to the triangular number growth.

Test Cases

# Provided examples
assert Solution().reachNumber(2) == 3  # minimum moves to reach 2
assert Solution().reachNumber(3) == 2  # minimum moves to reach 3

# Edge and additional cases
assert Solution().reachNumber(1) == 1  # direct reach in 1 move
assert Solution().reachNumber(-1) == 1  # negative target handled by symmetry
assert Solution().reachNumber(4) == 3  # sum 1+2+3=6, flip 1 to reach 4
assert Solution().reachNumber(10**9) > 0  # stress test for large target
assert Solution().reachNumber(-10**9) > 0  # stress test for large negative target

Test	Why
2	Small target requiring flips
3	Small target reached directly
1	Minimum positive target
-1	Minimum negative target handled symmetrically
4	Requires flipping one move to hit exactly
10^9	Tests algorithm performance on large input
-10^9	Tests performance and symmetry for large negative input

Edge Cases

Negative Target: If target is negative, the algorithm takes its absolute value. This is correct because left and right moves are symmetric.

Minimum Moves with Parity Adjustment: Sometimes the cumulative sum exceeds the target but the difference is odd. This requires additional moves until (sum - target) becomes even to allow flipping moves. This is crucial to avoid off-by-one errors.

Very Large Target: The target can be up to 10^9. The algorithm handles this efficiently because the sum grows quadratically, requiring roughly √10^9 ≈ 31622 iterations, which is feasible in real time. Memory usage remains constant.