LeetCode 754: Reach a Number

Problem Restatement

We start at position 0 on an infinite number line.

There is a destination at position target.

On move 1, we must move exactly 1 step.

On move 2, we must move exactly 2 steps.

On move 3, we must move exactly 3 steps.

In general, on move i, we must move exactly i steps.

For every move, we can choose either direction:

left or right

Return the minimum number of moves needed to reach exactly target.

Input and Output

Example function shape:

def reachNumber(target: int) -> int:
    ...

Examples

Example 1:

target = 2

Output:

3

One way to reach 2 in three moves is:

0 -> 1 -> -1 -> 2

The moves are:

So the answer is 3.

Example 2:

target = 3

Output:

2

We can move right twice:

0 -> 1 -> 3

The moves are:

So the answer is 2.

First Thought: Search All Paths

A direct idea is to explore all possible directions.

At move 1, we can go left or right.

At move 2, each of those choices branches again.

So after m moves, there are up to:

2^m

possible direction sequences.

That is too large.

We need to use the structure of the moves instead of searching every path.

Key Insight

The direction does not matter at first.

Suppose we always move right.

After m moves, our position is:

1 + 2 + 3 + ... + m

This sum is:

m * (m + 1) / 2

Call this sum s.

If s == target, then m moves are enough.

If s > target, we may be able to flip some moves from right to left.

Flipping a move of size x changes the final position by:

2 * x

because that move was contributing +x, and after flipping it contributes -x.

So the final position changes by an even number.

Therefore, after reaching a sum s, we can reach target exactly if:

s - target is even

If s - target is odd, no set of flipped moves can fix the difference yet.

So we keep adding the next move until:

1. s >= target
2. (s - target) is even

Why We Use Absolute Value

The number line is symmetric.

Reaching target = 5 takes the same number of moves as reaching target = -5.

Every right move can be replaced by a left move, and every left move can be replaced by a right move.

So we can solve only for:

target = abs(target)

Algorithm

1. Replace target with abs(target).
2. Start with:
   1. moves = 0
   2. position = 0
3. Keep adding the next move while either:
   1. position < target
   2. position - target is odd
4. Return moves.

In code, the loop condition is:

while position < target or (position - target) % 2 == 1:

Each iteration adds one more move:

moves += 1
position += moves

Walkthrough

Take:

target = 2

First use absolute value:

target = abs(2) = 2

Now keep moving right.

At move 3, the sum is 6.

The difference is:

6 - 2 = 4

Since 4 is even, we can flip moves whose total is:

4 / 2 = 2

That means flip the move of size 2.

Original all-right path:

+1 +2 +3 = 6

Flip +2 into -2:

+1 -2 +3 = 2

So 3 moves are enough.

Correctness

We solve for abs(target) because the movement rules are symmetric around 0. Any path to a positive target can be mirrored to reach the corresponding negative target with the same number of moves.

After m moves, if all moves go right, the farthest positive position is:

s = 1 + 2 + ... + m

Every other reachable position after m moves is formed by choosing some of these moves and flipping them from right to left.

If we flip moves with total length x, the final position becomes:

s - 2x

Therefore, a target is reachable after m moves exactly when s >= target and s - target is even.

The algorithm increases m from 0 upward and stops at the first m satisfying these two conditions.

Since smaller values of m were checked and failed, the returned number of moves is minimal.

Complexity

The sum after m moves is about m^2 / 2, so we need about sqrt(target) moves before crossing the target.

Implementation

class Solution:
    def reachNumber(self, target: int) -> int:
        target = abs(target)

        moves = 0
        position = 0

        while position < target or (position - target) % 2 == 1:
            moves += 1
            position += moves

        return moves

Code Explanation

We first reduce the problem to the positive side:

target = abs(target)

Then we keep track of how many moves we have taken:

moves = 0

and the farthest position we can reach by moving right every time:

position = 0

The loop continues while the current all-right sum cannot be adjusted to exactly reach target:

while position < target or (position - target) % 2 == 1:

There are two bad cases.

First, if position < target, we have not gone far enough yet.

Second, if position - target is odd, then flipping moves cannot fix the difference, because every flip changes the position by an even amount.

Inside the loop, we add the next move:

moves += 1
position += moves

When the loop stops, position >= target and position - target is even.

That means we can flip some moves to land exactly on target.

So we return:

return moves

Testing

def run_tests():
    s = Solution()

    assert s.reachNumber(2) == 3
    assert s.reachNumber(3) == 2
    assert s.reachNumber(1) == 1
    assert s.reachNumber(4) == 3
    assert s.reachNumber(5) == 5
    assert s.reachNumber(-2) == 3
    assert s.reachNumber(-3) == 2

    print("all tests passed")

run_tests()

Test meaning: