Reaching Points

Hard
1279.

Reaching Points

Reaching Points is a hard coding problem on math and number theory, asked in Amazon, Google and Goldman Sachs interviews.

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
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} sx
 * @param {number} sy
 * @param {number} tx
 * @param {number} ty
 * @return {boolean}
 */
var reachingPoints = function(sx, sy, tx, ty) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

  1. Hint 1

    Searching forwards branches two ways at every step. Look at the target instead: how many points can move to (tx, ty)?

  2. Hint 2

    Both coordinates stay positive, so if tx > ty the last move must have added ty to the first coordinate — the predecessor is unique.

  3. Hint 3

    Repeated subtraction of ty from tx is 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

  1. While tx > sx and ty > sy: if tx > ty set tx %= ty, otherwise set ty %= tx.
  2. If now tx == sx, the remaining moves can only have added sx to the second coordinate: return whether ty >= sy and (ty - sy) % sx == 0.
  3. If ty == sy, symmetrically return whether tx >= sx and (tx - sx) % sy == 0.
  4. 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 %= ty when ty == sy can jump past sx; switch to the divisibility check as soon as a coordinate matches.
  • A point with equal coordinates other than the start is unreachable, and x % x becomes 0 — make sure the loop then reports false.

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 False

Java

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.

All 337 math problems · the whole catalogue