#754

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Reach a Number

Determine the minimum number of moves to reach a target on an infinite number line using step increments, leveraging binary search.

math binary search

Problem Statement

You start at position 0 on an infinite number line. There is a destination located at an integer position called target, which can be positive or negative. On each move, you can go left or right, and the length of each move increases by 1 sequentially, starting from 1. Determine the minimum number of moves required to reach the target exactly.

For example, with target = 2, a sequence of moves could be: move 1 to the right, move 2 to the left, and move 3 to the right, totaling 3 moves. Your task is to compute the minimal move count to reach any given target using the incremental step pattern, optimizing via binary search over the number of moves.

Examples

Example 1

Input: target = 2

Output: 3

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

Input: target = 3

Output: 2

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

-109 <= target <= 109
target != 0

Solution Approach

Normalize target and use cumulative sum

Convert the target to its absolute value since the number line is symmetric. Use the formula for the sum of the first n integers to find the minimum moves whose cumulative sum can potentially reach or exceed the target.

Binary search for minimum move count

Perform binary search on the move count space, checking if the cumulative sum minus the target is even, which ensures a valid sequence of left and right moves. This exploits the pattern that only certain sums allow reaching the exact target.

Handle parity adjustments

If the cumulative sum exceeds the target but the difference is odd, increment the move count until the difference between the sum and target is even. This guarantees that flipping a move direction can reach the exact target, addressing a common failure mode in naive sum calculations.

Complexity Analysis

Metric	Value
Time	O(\sqrt{\text{target}})
Space	O(1)

The algorithm runs in O(\sqrt{target}) time because the sum of first n integers grows quadratically, allowing binary search to converge quickly. Space usage is O(1) since calculations are done using arithmetic variables without extra storage.

What Interviewers Usually Probe

Ask why the cumulative sum minus target parity matters for valid sequences.
Probe if the candidate considers both positive and negative targets efficiently.
Check if they identify the quadratic growth of sums and optimize using binary search instead of linear iteration.

Common Pitfalls or Variants

Common pitfalls

Ignoring the parity condition can lead to incorrect minimal move counts.
Attempting a linear search over moves without exploiting cumulative sum patterns wastes time.
Failing to normalize the target can cause redundant calculations for negative positions.

Follow-up variants

Find the minimal moves to reach multiple targets simultaneously using the same incremental move pattern.
Compute the number of distinct sequences of moves that reach the target with minimal steps.
Extend to restricted moves where certain step sizes are forbidden, requiring adjustments in the binary search.

FAQ

Why do we take the absolute value of the target in Reach a Number?

Taking the absolute value leverages the symmetry of the number line, reducing the problem to a positive target while preserving the correct minimal move calculation.

How does binary search optimize finding the minimum moves?

Binary search narrows the candidate move count efficiently by checking cumulative sums, avoiding linear iteration and quickly locating the smallest valid number of steps.

What happens if the cumulative sum minus target is odd?

If the difference is odd, you cannot flip any subset of moves to reach the target exactly, so additional moves are required until the difference becomes even.

Can this approach handle negative targets?

Yes, by normalizing the target to its absolute value, the algorithm works identically due to symmetry, ensuring minimal move calculation is correct for all integers.

What is the key pattern exploited in Reach a Number?

The problem leverages the pattern that the sum of the first n integers must exceed the target and the excess must be even, allowing flipping moves to hit the exact target.

terminal

Solution

Solution 1: Mathematical Analysis

Due to symmetry, each time we can choose to move left or right, so we can take the absolute value of $\textit{target}$.

1

2

3

4

5

6

7

8

9

class Solution:
    def reachNumber(self, target: int) -> int:
        target = abs(target)
        s = k = 0
        while 1:
            if s >= target and (s - target) % 2 == 0:
                return k
            k += 1
            s += k

Continue Practicing

#793 preimage size of factorial zeroes function #710 random pick with blacklist #668 kth smallest number in multiplication table