Check if Point Is Reachable

Hard
1320.

Check if Point Is Reachable

Check if Point Is Reachable is a hard coding problem on math and number theory, asked in Amazon, Google and PhonePe interviews.

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
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} targetX
 * @param {number} targetY
 * @return {boolean}
 */
var isReachable = function(targetX, targetY) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

  1. Hint 1

    Look for an invariant. What happens to gcd(x, y) under each move?

  2. Hint 2

    Subtracting one coordinate from the other keeps the gcd; doubling one coordinate multiplies the gcd by 1 or 2.

  3. 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

  1. Compute g = gcd(targetX, targetY) with Euclid's algorithm.
  2. Return true exactly when g is 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)) == 0

Java

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.

All 337 math problems · the whole catalogue