Reach a Number

Medium Binary Search Binary Search on Answer Space Original on LeetCode

Reported atMeeshoInMobi

Reach a Number is a medium binary search problem solved with the binary search on answer space pattern. The best approach, optimal (binary search on the move count), runs in O(log t) time and O(1) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (track every reachable position) up.

Problem

You stand at position 0 on an infinite number line and want to reach position target.

You make moves numbered 1, 2, 3, …. On move i you must walk exactly i steps, but you may choose to go either left or right. Return the minimum number of moves needed to land exactly on target.

Examples

Example 1

Input
target = 4
Output
3
Why
Move -1, +2, +3: positions 0 → -1 → 1 → 4. Two moves reach at most 1 + 2 = 3, so three are needed.

Example 2

Input
target = -6
Output
3
Why
Move -1, -2, -3. By symmetry, reaching -6 costs the same as reaching 6, and 1 + 2 + 3 = 6 exactly.

Example 3

Input
target = 5
Output
5
Why
Sums after 3 and 4 moves are 6 and 10, both even, while 5 is odd. After 5 moves the sum is 15 and 15 - 5 = 10; flipping +5 to -5 gives 1 + 2 + 3 + 4 - 5 = 5.

Constraints

  • -10^9 <= target <= 10^9
  • target != 0

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 16 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (track every reachable position)O(t^1.5)O(t)
Better (add moves until the gap is even)O(√t)O(1)
Optimal (binary search on the move count)O(log t)O(1)

1Brute force (track every reachable position)

TimeO(t^1.5)About √t rounds, and after k rounds the set holds up to k(k + 1) / 2 ≈ t positions.
SpaceO(t)The set of positions, which spans [-sum, sum] with one parity.

Keep the set of positions reachable after i moves. Move i + 1 turns each position p into p + (i + 1) and p - (i + 1). Stop at the first move count whose set contains the target.

  1. positions = {0}, moves = 0.
  2. While target is not in positions: moves++, positions = {p ± moves for p in positions}.
  3. Return moves.
class Solution {
    public int reachNumber(int target) {
        Set<Long> positions = new HashSet<>();
        positions.add(0L);
        int moves = 0;
        while (!positions.contains((long) target)) {
            moves++;
            Set<Long> next = new HashSet<>();
            for (long p : positions) {
                next.add(p + moves);
                next.add(p - moves);
            }
            positions = next;
        }
        return moves;
    }
}

2Better (add moves until the gap is even)

TimeO(√t)The sum grows quadratically, so about √(2t) moves reach t, plus at most two more.
SpaceO(1)Two counters.

Work with t = |target|. Keep adding moves k = 1, 2, 3, … to a running sum. Stop as soon as sum >= t and (sum - t) is even: flipping the move of size (sum - t) / 2 (or a set of moves adding up to it) lands exactly on t.

  1. t = |target|, k = 0, sum = 0.
  2. While sum < t or (sum - t) is odd: k++, sum += k.
  3. Return k.
class Solution {
    public int reachNumber(int target) {
        long t = Math.abs((long) target), sum = 0;
        int k = 0;
        while (sum < t || (sum - t) % 2 != 0) {
            k++;
            sum += k;
        }
        return k;
    }
}

3Optimal (binary search on the move count)

TimeO(log t)About 18 binary-search rounds plus at most two parity steps.
SpaceO(1)A few 64-bit integers.

The triangular sum k(k + 1) / 2 is increasing in k, so binary search for the smallest k whose sum reaches t = |target|. Then fix the parity: if sum - t is odd, one more move (k + 1) fixes it when k + 1 is odd, otherwise two more moves are needed.

  1. t = |target|; binary search lo = 0, hi = 2 × 10^5 for the smallest k with k(k + 1) / 2 >= t (use 64-bit math).
  2. While (k(k + 1) / 2 - t) is odd: k++ (this runs at most twice).
  3. Return k.
class Solution {
    public int reachNumber(int target) {
        long t = Math.abs((long) target);
        long lo = 0, hi = 200000;
        while (lo < hi) {
            long mid = (lo + hi) / 2;
            if (mid * (mid + 1) / 2 >= t) hi = mid;
            else lo = mid + 1;
        }
        long k = lo;
        while ((k * (k + 1) / 2 - t) % 2 != 0) k++;
        return (int) k;
    }
}

Edge cases to test

  • Negative targets: the answer equals the one for |target|
  • Targets that are triangular numbers (1, 3, 6, 10, …) need no flips
  • An odd gap between the running sum and the target: one or two extra moves are needed
  • Large targets around 10^9: the triangular sum exceeds 32 bits, use 64-bit arithmetic

Hints

Hint 1

Only |target| matters. If every move went right, after k moves you would be at 1 + 2 + … + k.

Hint 2

Flipping move i from right to left lowers the final position by exactly 2i. So you can hit target after k moves when the sum is at least target and sum - target is even.

Hint 3

Find the smallest k with k(k + 1) / 2 >= target, then add moves until the gap becomes even; that takes at most two extra moves.

FAQ

What is the best time complexity for Reach a Number?

Optimal (binary search on the move count) runs in O(log t) time and O(1) extra space. About 18 binary-search rounds plus at most two parity steps.

Which pattern does Reach a Number use?

It is a binary search problem that uses the binary search on answer space pattern. Other problems with the same pattern: Koko Eating Bananas, Minimum Number of Days to Make m Bouquets, Separate Squares I.

Is there a brute force solution for Reach a Number?

Yes. Brute force (track every reachable position) takes O(t^1.5) time and O(t) space. Keep the set of positions reachable after i moves.

Which edge cases should I test for Reach a Number?

Negative targets: the answer equals the one for |target|; Targets that are triangular numbers (1, 3, 6, 10, …) need no flips; An odd gap between the running sum and the target: one or two extra moves are needed; Large targets around 10^9: the triangular sum exceeds 32 bits, use 64-bit arithmetic.