Check if Point Is Reachable — Solution in Python, Java & C++
Check if Point Is Reachable solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Check if Point Is Reachable is a hard coding problem on math and number theory, asked in Amazon, Google and PhonePe interviews.
- Difficulty: Hard
- Topics: Math, Number Theory
- Asked at: Amazon, Google, PhonePe
- 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
A token starts at the point (1, 1) of an infinite grid. From (x, y) one step can move it to any of:
(x, y - x)(x - y, y)(2 * x, y)(x, 2 * y)
Given a target (targetX, targetY), return true if the token can reach it in a finite number of steps.
Example 1
Input: targetX = 6, targetY = 10
Output: true
Explanation: One route: (1,1) → (2,1) → (4,1) → (3,1) → (3,2) → (3,4) → (3,8) → (3,5) → (3,10) → (6,10).
Example 2
Input: targetX = 12, targetY = 18
Output: false
Explanation: gcd(12, 18) = 6, and the odd factor 3 can never appear.
Example 3
Input: targetX = 1, targetY = 1
Output: true
Constraints
1 <= targetX, targetY <= 10^9
Hints for Check if Point Is Reachable
Hint 1
Look for an invariant. What happens to
gcd(x, y)under each move?Hint 2
Subtracting one coordinate from the other keeps the gcd; doubling one coordinate multiplies the gcd by 1 or 2.
Hint 3
So every reachable point has a power-of-two gcd — and conversely every such point is reachable. Check whether
gcd(targetX, targetY)is a power of two.
How to solve Check if Point Is Reachable
The gcd of the two coordinates starts at 1, is unchanged by the subtraction moves and at most doubles under the doubling moves — so it is always a power of two. That condition is also sufficient.
Approach
- Compute
g = gcd(targetX, targetY)with Euclid's algorithm. - Return
trueexactly whengis a power of two, i.e.g & (g - 1) == 0.
Why it works
Necessity: gcd(x, y - x) = gcd(x, y), and gcd(2x, y) is gcd(x, y) or twice it, so from gcd = 1 only powers of two can appear. Sufficiency: work backwards from the target, where the reverse moves are (x, y) → (x, x + y), (x + y, y) and halving an even coordinate. Halve while a coordinate is even; when both are odd and different, replace the larger by their sum, which is even, and halve again — the larger coordinate strictly shrinks each round. This ends at (g', g') where g' is the odd part of the gcd, which is 1 exactly when the gcd is a power of two, i.e. at (1, 1).
Complexity
- Time —
O(log min(targetX, targetY)) - Space —
O(1)
Pitfalls
- A search over the grid never terminates on its own — coordinates can grow without bound; the invariant is the whole solution.
- 1 is a power of two (2^0), so coprime targets are reachable.
- In Python, PHP and Ruby
&binds differently from==; parenthesise(g & (g - 1)) == 0.
Reference solution
Python
import math
def isReachable(targetX: int, targetY: int) -> bool:
g = math.gcd(targetX, targetY)
return (g & (g - 1)) == 0Java
public static boolean isReachable(int targetX, int targetY) {
int a = targetX, b = targetY;
while (b != 0) { int t = a % b; a = b; b = t; }
return (a & (a - 1)) == 0;
}C++
bool isReachable(int targetX, int targetY) {
int a = targetX, b = targetY;
while (b != 0) { int t = a % b; a = b; b = t; }
return (a & (a - 1)) == 0;
}JavaScript
var isReachable = function(targetX, targetY) {
var a = targetX, b = targetY;
while (b !== 0) { var t = a % b; a = b; b = t; }
return (a & (a - 1)) === 0;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.