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 <= 1000000000target is not 0.
Hints for Reach a Number
Hint 1
The problem is symmetric about zero — replace
targetwith|target|.Hint 2
After
kmoves the reachable positions are exactly those with the same parity as1+2+…+kand magnitude at most that sum.Hint 3
Flipping a move of size
ifrom right to left changes the total by2i— 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
- Replace
targetwith its absolute value — left and right are symmetric. - Grow
kfrom 0, accumulatingsum = 1 + 2 + … + k. - Stop at the first
kwheresum >= targetand(sum - target)is even. - 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 >= targetignores the parity condition and undercounts, e.g.target = 2would answer 2. - Forgetting the absolute value makes negative targets loop forever.
- The loop runs about
sqrt(2·10^9) ≈ 63,000times 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 kJava
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