Check if Point Is Reachable

Hard Bit Manipulation Math / Number Theory Original on LeetCode

Reported atPhonePe

Check if Point Is Reachable is a hard bit manipulation problem solved with the math / number theory pattern. The best approach, optimal (gcd must be a power of two), runs in O(log M) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (shrink the target step by step) up.

Problem

You stand on the point (1, 1) of an infinite grid and want to reach (targetX, targetY). From a point (x, y) one step can take you to any of:

  • (x, y - x) or (x - y, y) (subtract one coordinate from the other),
  • (2 * x, y) or (x, 2 * y) (double one coordinate).

Return true if the target can be reached with some finite sequence of steps, and false otherwise.

Examples

Example 1

Input
targetX = 4, targetY = 7
Output
true
Why
(1,1) → (1,2) → (1,4) → (1,8) → (1,7) → (2,7) → (4,7): three doublings, one subtraction, then two more doublings.

Example 2

Input
targetX = 6, targetY = 9
Output
false
Why
Both coordinates are multiples of 3, but every point reachable from (1, 1) has a gcd with no odd factor.

Example 3

Input
targetX = 1, targetY = 1
Output
true
Why
You are already standing on the target.

Constraints

  • 1 <= targetX, targetY <= 10^9

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (shrink the target step by step)O(log² M)O(1)
Optimal (gcd must be a power of two)O(log M)O(1)

1Brute force (shrink the target step by step)

TimeO(log² M)Every subtraction makes a coordinate even, so it is followed by at least one halving; the values shrink geometrically, with M = max(targetX, targetY).
SpaceO(1)Two integer variables.

The target is reachable exactly when its two coordinates share no odd factor (see the optimal approach for why). Test that by shrinking the pair with operations that keep the odd part of the gcd unchanged: halve an even coordinate, and when both are odd and different, replace the larger by the difference with the smaller (the result is even, so it is halved next). If both coordinates become equal and odd but are not 1, that value is a shared odd factor and the answer is false; reaching (1, 1) means the answer is true.

  1. Let x = targetX, y = targetY.
  2. While (x, y) is not (1, 1):
  3. If x is even, x /= 2; else if y is even, y /= 2.
  4. Else if x == y (both odd, above 1), return false.
  5. Else subtract the smaller from the larger.
  6. Return true.
class Solution {
    public boolean isReachable(int targetX, int targetY) {
        int x = targetX, y = targetY;
        while (x != 1 || y != 1) {
            if (x % 2 == 0) x /= 2;
            else if (y % 2 == 0) y /= 2;
            else if (x == y) return false;
            else if (x > y) x -= y;
            else y -= x;
        }
        return true;
    }
}

2Optimal (gcd must be a power of two)

TimeO(log M)Euclid's algorithm takes a logarithmic number of modulo steps.
SpaceO(1)Two integer variables.

The moves (x, y - x) and (x - y, y) keep the gcd unchanged, and doubling a coordinate can only multiply the gcd by 2 or leave it alone. Starting from gcd 1, every reachable point therefore has a gcd that is a power of two. The converse also holds: from (1, 1) you can reach (1, 2^k) and subtract to get (1, m) for any m, and combining subtraction with doubling lets you rebuild any pair whose gcd is a power of two (exactly the pairs the first approach shrinks to (1, 1)). So the answer is simply whether g = gcd(targetX, targetY) is a power of two, which is (g & (g - 1)) == 0.

  1. Compute g = gcd(targetX, targetY) with Euclid's algorithm.
  2. Return (g & (g - 1)) == 0.
class Solution {
    public 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;
    }
}

Edge cases to test

  • The target is the start point (1, 1)
  • Equal coordinates, like (8, 8) (reachable) or (3, 3) (not reachable)
  • One coordinate is 1, which always makes the gcd 1
  • Both coordinates are large powers of two
  • Large coprime odd coordinates near 10^9

Hints

Hint 1

Look at the greatest common divisor. Subtracting one coordinate from the other never changes it, and doubling a coordinate can only add factors of two.

Hint 2

So an odd factor shared by both coordinates can never appear when you start from (1, 1). Is the converse also true: can every point whose gcd is a power of two be reached?

Hint 3

To test the condition without computing a gcd, shrink the target: halve an even coordinate, and when both are odd and different, replace the larger by the difference (which becomes even). Neither operation changes the odd part of the gcd, and you end at (1, 1) exactly when that odd part is 1.

FAQ

What is the best time complexity for Check if Point Is Reachable?

Optimal (gcd must be a power of two) runs in O(log M) time and O(1) extra space. Euclid's algorithm takes a logarithmic number of modulo steps.

Which pattern does Check if Point Is Reachable use?

It is a bit manipulation problem that uses the math / number theory pattern.

Is there a brute force solution for Check if Point Is Reachable?

Yes. Brute force (shrink the target step by step) takes O(log² M) time and O(1) space. The target is reachable exactly when its two coordinates share no odd factor (see the optimal approach for why).

Which edge cases should I test for Check if Point Is Reachable?

The target is the start point (1, 1); Equal coordinates, like (8, 8) (reachable) or (3, 3) (not reachable); One coordinate is 1, which always makes the gcd 1; Both coordinates are large powers of two; Large coprime odd coordinates near 10^9.