Reaching Points — Solution in Python, Java & C++
Reaching Points solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem on math and number theory.
Reaching Points is a hard coding problem on math and number theory, asked in Amazon, Google and Goldman Sachs interviews.
- Difficulty: Hard
- Topics: Math, Number Theory
- Asked at: Amazon, Google, Goldman Sachs
- 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
From a point (x, y) one move takes you to either (x, x + y) or (x + y, y).
Given a start (sx, sy) and a target (tx, ty), return true if some sequence of zero or more moves turns the start into the target, and false otherwise.
Example 1
Input: sx = 1, sy = 1, tx = 3, ty = 5
Output: true
Explanation: (1, 1) → (1, 2) → (3, 2) → (3, 5).
Example 2
Input: sx = 1, sy = 1, tx = 2, ty = 2
Output: false
Example 3
Input: sx = 1, sy = 1, tx = 1, ty = 1
Output: true
Explanation: Zero moves are allowed.
Constraints
1 <= sx, sy, tx, ty <= 10^9
Hints for Reaching Points
Hint 1
Searching forwards branches two ways at every step. Look at the target instead: how many points can move to
(tx, ty)?Hint 2
Both coordinates stay positive, so if
tx > tythe last move must have addedtyto the first coordinate — the predecessor is unique.Hint 3
Repeated subtraction of
tyfromtxis a modulo. Be careful when one coordinate already equals its start value: then check divisibility instead of reducing past it.
How to solve Reaching Points
Run the moves backwards: the larger coordinate must have been produced by adding the smaller one, so the path back is unique and can be compressed with modulo, like the Euclidean algorithm.
Approach
- While
tx > sxandty > sy: iftx > tysettx %= ty, otherwise setty %= tx. - If now
tx == sx, the remaining moves can only have addedsxto the second coordinate: return whetherty >= syand(ty - sy) % sx == 0. - If
ty == sy, symmetrically return whethertx >= sxand(tx - sx) % sy == 0. - Otherwise one coordinate dropped below its start: return
false.
Why it works
Moves keep both coordinates positive and strictly increase one of them, so a point (x, y) with x > y can only come from (x - y, y) and one with x < y only from (x, y - x); a point with x == y has no predecessor. Hence the backward walk is forced. While both coordinates are still above their starts, the walk must keep subtracting, and a run of subtractions of ty from tx stops exactly when tx < ty, i.e. at tx % ty — so the modulo skips the run without missing the start (the start cannot appear mid-run, because there ty > sy). Once a coordinate equals its start it must stay fixed, so the other one has to come down to its start in steps of exactly that value.
Complexity
- Time —
O(log max(tx, ty)) - Space —
O(1)
Pitfalls
- Subtracting one step at a time is correct but takes 10^9 steps for (1, 1) → (10^9, 1).
- Reducing
tx %= tywhenty == sycan jump pastsx; switch to the divisibility check as soon as a coordinate matches. - A point with equal coordinates other than the start is unreachable, and
x % xbecomes 0 — make sure the loop then reportsfalse.
Reference solution
Python
def reachingPoints(sx: int, sy: int, tx: int, ty: int) -> bool:
while tx > sx and ty > sy:
if tx > ty:
tx %= ty
else:
ty %= tx
if tx == sx:
return ty >= sy and (ty - sy) % sx == 0
if ty == sy:
return tx >= sx and (tx - sx) % sy == 0
return FalseJava
public static boolean reachingPoints(int sx, int sy, int tx, int ty) {
while (tx > sx && ty > sy) {
if (tx > ty) tx %= ty;
else ty %= tx;
}
if (tx == sx) return ty >= sy && (ty - sy) % sx == 0;
if (ty == sy) return tx >= sx && (tx - sx) % sy == 0;
return false;
}C++
bool reachingPoints(int sx, int sy, int tx, int ty) {
while (tx > sx && ty > sy) {
if (tx > ty) tx %= ty;
else ty %= tx;
}
if (tx == sx) return ty >= sy && (ty - sy) % sx == 0;
if (ty == sy) return tx >= sx && (tx - sx) % sy == 0;
return false;
}JavaScript
var reachingPoints = function(sx, sy, tx, ty) {
while (tx > sx && ty > sy) {
if (tx > ty) tx %= ty;
else ty %= tx;
}
if (tx === sx) return ty >= sy && (ty - sy) % sx === 0;
if (ty === sy) return tx >= sx && (tx - sx) % sy === 0;
return false;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.