Reach a Number: Greedy Steps with Parity Flip

You are standing at position 0 on an infinite number line. On step i, you move exactly i positions either left or right. Given a target, find the minimum number of steps to reach it.

This is LeetCode 754: Reach a Number, and it is one of those problems that looks like it needs backtracking or BFS but actually has a clean O(sqrt(n)) math solution. The trick is a parity argument that lets you skip the brute-force search entirely.

The key insight: keep taking steps to the right (1 + 2 + 3 + ... + k) until you reach or pass the target. If the overshoot is even, you can flip exactly one earlier step from right to left, and the sum drops by exactly twice that step's size, landing you on the target.

Problem statement

You start at position 0 on a number line. On step i (starting at 1), you can move either +i (right) or -i (left). Given an integer target, return the minimum number of steps to reach target.

For example, with target = 3, you can go +1, +2 to reach position 3 in 2 steps. With target = 2, the minimum is 3 steps: +1, -2, +3 lands on position 2.

Approach: greedy with parity check

The first observation is that target and -target require the same number of steps (the number line is symmetric around 0). So you can work with abs(target) and only think about reaching a positive value.

Next, imagine you greedily take every step to the right: the running sum after k steps is 1 + 2 + 3 + ... + k = k*(k+1)/2. There are three cases:

1. sum equals target: You are done. Every step went right and you landed exactly on the target.
2. sum exceeds target by an even amount: Let the overshoot be sum - target. If you flip a single step of size (sum - target) / 2 from right to left, that subtracts 2 * ((sum - target) / 2) = sum - target from the total, making the new sum equal to target. You still used k steps.
3. sum exceeds target by an odd amount: No single flip can fix an odd overshoot, because flipping any step changes the sum by an even number (2 times the step size). So you take one or two more steps until the overshoot becomes even, then flip.

That is the entire algorithm. No recursion, no DP table, no BFS. Just keep adding steps and check the parity of the overshoot.

def reach_number(target):
    target = abs(target)
    step = 0
    total = 0

    while total < target or (total - target) % 2 != 0:
        step += 1
        total += step

    return step

Visual walkthrough

The walkthrough above traces target = 2. After steps 1 and 2, the sum is 3 and the overshoot is 1 (odd), so no flip works. After step 3, the sum is 6 and the overshoot is 4 (even). Flip the step of size 2 to go left instead of right, subtracting 4 from the total. The result: positions 0, 1, -1, 2. Three steps to reach 2.

Complexity analysis

The loop runs at most O(sqrt(target)) iterations, and each iteration does constant work. No extra data structures are needed.

Building blocks

1. Prefix sum / triangular numbers

The running sum 1 + 2 + ... + k is the k-th triangular number, k*(k+1)/2. Recognizing this formula lets you estimate how many steps you need before starting: solve k*(k+1)/2 >= target to get k roughly equal to sqrt(2 * target).

k = int((-1 + (1 + 8 * target) ** 0.5) / 2)

This gives a starting estimate. In the actual solution you just increment step in a loop, but understanding the math tells you why the loop is O(sqrt(target)) rather than O(target).

2. Parity argument for step flipping

The parity argument is the core insight. Flipping step s from +s to -s changes the sum by 2s. Since 2s is always even, the overshoot must be even for a valid flip to exist. If the overshoot is odd after reaching or passing the target, you need one or two more steps to make it even.

overshoot = total - target
if overshoot % 2 == 0:
    flip_step = overshoot // 2

The step you flip has size overshoot // 2, and it must be one of the steps you already took (between 1 and k). Since overshoot = total - target and total = k*(k+1)/2, the value overshoot // 2 is always <= k, so a valid step to flip always exists.

Edge cases

• target = 0: No steps needed. The answer is 0 since you start at position 0.
• Negative target: Use abs(target). The number line is symmetric, so reaching -5 takes the same steps as reaching 5.
• Exact match on first pass: When 1 + 2 + ... + k equals the target exactly, the overshoot is 0 (even), so no flip is needed.
• Overshoot needs two extra steps: If the overshoot is odd after step k, adding step k+1 may keep it odd (if k+1 is even). In that case, step k+2 always fixes it, because adding two consecutive integers changes parity.
• Large target: The solution handles any target within 32-bit integer range efficiently, since the loop runs in O(sqrt(target)) time.

From understanding to recall

The parity flip trick feels almost magical the first time you see it. But that is exactly the kind of insight that slips away if you do not revisit it. Two weeks from now, will you remember that flipping a step changes the sum by an even number, and that the overshoot must therefore be even? Or will you stare at this problem again and reach for BFS?

Spaced repetition locks in these "aha" moments. You solve the problem once, then come back to it at increasing intervals. Each time, you rebuild the parity argument from scratch. After a few reps, the technique is automatic. CodeBricks organizes problems by their underlying building blocks and schedules reviews so the pattern stays fresh without wasting time on problems you already know.

Related posts

• Climbing Stairs - A step-counting problem that builds intuition for how choices at each step affect the total
• Reverse Integer - Another math-focused problem where digit manipulation and overflow reasoning are the main challenge
• Coin Change - Reaching a target value by choosing from a set of options, solved with DP instead of a greedy parity trick