Reach a Number

Medium
551.

Reach a Number

Reach a Number is a medium coding problem on math and binary search, asked in Amazon and Google interviews.

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

On the i-th move (1-indexed) you take exactly i steps, choosing to go left or right. Return the minimum number of moves needed to land exactly on target.

Example 1

Input
target = 2
Output
3
Explanation
Go right to 1, left to -1, then right 3 to 2.

Example 2

Input
target = 3
Output
2
Explanation
Right 1 to 1, then right 2 to 3.

Example 3

Input
target = -5
Output
5

Constraints

  • -1000000000 <= target <= 1000000000
  • target is not 0.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} target
 * @return {number}
 */
var reachNumber = function(target) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Reach a Number — Solution in Python, Java & C++

Reach a Number solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on math and binary search.

Reach a Number is a medium coding problem on math and binary search, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Math, Binary Search
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

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

On the i-th move (1-indexed) you take exactly i steps, choosing to go left or right. Return the minimum number of moves needed to land exactly on target.

Example 1

Input: target = 2
Output: 3
Explanation: Go right to 1, left to -1, then right 3 to 2.

Example 2

Input: target = 3
Output: 2
Explanation: Right 1 to 1, then right 2 to 3.

Example 3

Input: target = -5
Output: 5

Constraints

  • -1000000000 <= target <= 1000000000
  • target is not 0.

Hints for Reach a Number

  1. Hint 1

    The problem is symmetric about zero — replace target with |target|.

  2. Hint 2

    After k moves the reachable positions are exactly those with the same parity as 1+2+…+k and magnitude at most that sum.

  3. Hint 3

    Flipping a move of size i from right to left changes the total by 2i — always an even amount.

How to solve Reach a Number

After k moves the maximum reach is S = k(k+1)/2, and flipping any move changes the total by an even number. So target is reachable in k moves exactly when S >= |target| and S - |target| is even.

Approach

  1. Replace target with its absolute value — left and right are symmetric.
  2. Grow k from 0, accumulating sum = 1 + 2 + … + k.
  3. Stop at the first k where sum >= target and (sum - target) is even.
  4. Return that k.

Why it works

Flipping the move of size i reduces the total by 2i, so from S you can reach exactly the values S, S-2, S-4, … down to -S — every value of the same parity as S within range. Hence both conditions are necessary and together sufficient.

Complexity

  • Time — O(sqrt(target))
  • Space — O(1)

Pitfalls

  • Stopping as soon as sum >= target ignores the parity condition and undercounts, e.g. target = 2 would answer 2.
  • Forgetting the absolute value makes negative targets loop forever.
  • The loop runs about sqrt(2·10^9) ≈ 63,000 times at the limit plus at most two extra steps — comfortably fast.

Reference solution

Python

def reachNumber(target: int) -> int:
    t = abs(target)
    k = 0
    total = 0
    while total < t or (total - t) % 2 != 0:
        k += 1
        total += k
    return k

Java

public static int reachNumber(int target) {
    long t = Math.abs((long) target);
    long k = 0, sum = 0;
    while (sum < t || (sum - t) % 2 != 0) {
        k++;
        sum += k;
    }
    return (int) k;
}

C++

int reachNumber(int target) {
    long long t = target < 0 ? -(long long) target : (long long) target;
    long long k = 0, sum = 0;
    while (sum < t || (sum - t) % 2 != 0) {
        k++;
        sum += k;
    }
    return (int) k;
}

JavaScript

var reachNumber = function(target) {
    const t = Math.abs(target);
    let k = 0, sum = 0;
    while (sum < t || (sum - t) % 2 !== 0) {
        k++;
        sum += k;
    }
    return k;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue

Learn the technique: Binary Search