LeetCode 2543 - Check if Point Is Reachable

LeetCode Problem 2543

Difficulty: 🔴 Hard
Topics: Math, Number Theory

Solution

Problem Understanding

The problem gives us an infinite two dimensional grid and asks whether we can travel from the starting point (1, 1) to a target point (targetX, targetY) using a specific set of operations.

From any point (x, y), we may perform one of four moves:

• Subtract x from y, producing (x, y - x)
• Subtract y from x, producing (x - y, y)
• Double x, producing (2x, y)
• Double y, producing (x, 2y)

The task is to determine whether the target point can be reached after some finite number of operations.

The input consists of two integers:

• targetX, the target x-coordinate
• targetY, the target y-coordinate

The output is a boolean:

• true if the target is reachable
• false otherwise

The constraints are very important:

1 <= targetX, targetY <= 10^9

Because the coordinates may be as large as one billion, any brute force search through the state space is impossible. The grid is infinite, and the number of reachable intermediate states grows extremely quickly.

A few observations immediately stand out:

• Coordinates always remain integers.
• The subtraction operations resemble the Euclidean algorithm for computing the greatest common divisor.
• Doubling operations only introduce powers of two.
• Reachability likely depends on some invariant property that never changes during valid moves.

Important edge cases include:

• When one coordinate is 1
• When both coordinates are equal
• Very large powers of two
• Pairs whose greatest common divisor contains odd factors
• Minimal input (1,1)

These cases help expose the mathematical structure behind the problem.

Approaches

Brute Force Approach

A natural first idea is to model the problem as a graph search. Each point (x, y) is a node, and every allowed operation creates an edge to another node.

Starting from (1,1), we could use BFS or DFS to explore reachable states until we either:

• Reach (targetX, targetY)
• Exhaust all possible states

This approach is correct because graph traversal systematically explores every valid sequence of operations.

However, this method is completely impractical.

The coordinates may grow extremely large because of repeated doubling operations. Even if we impose bounds such as limiting coordinates to at most targetX and targetY, the number of states is still enormous. A BFS would potentially examine billions of points.

Additionally, subtraction operations create many overlapping paths and cycles, making the state graph highly connected.

Therefore, brute force cannot work within the constraints.

Key Insight

The key insight is that the operations preserve a very specific mathematical property involving the greatest common divisor.

Consider the subtraction operations:

gcd(x, y) = gcd(x, y - x)
gcd(x, y) = gcd(x - y, y)

These are exactly the transformations used in the Euclidean algorithm.

Now consider the doubling operations:

gcd(2x, y)
gcd(x, 2y)

Doubling may multiply the gcd by 2, but it cannot introduce any odd prime factor.

Since we start from (1,1), whose gcd is:

gcd(1,1) = 1

the only factors we can ever introduce into the gcd are powers of two.

That means:

gcd(targetX, targetY)

must be a power of two for the target to be reachable.

This turns the entire problem into a simple number theory check.

If the gcd is:

1, 2, 4, 8, 16, ...

then the point is reachable.

Otherwise, it is impossible.

We can check whether a number is a power of two using the classic bit trick:

g & (g - 1) == 0

where g is the gcd.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Explores enormous state graph of reachable coordinates
Optimal	O(log(min(targetX, targetY)))	O(1)	Uses gcd invariant and power-of-two property

Algorithm Walkthrough

Optimal Algorithm

1. Compute the greatest common divisor of targetX and targetY.

The subtraction operations preserve the gcd, while doubling operations only multiply it by powers of two. Therefore, the gcd completely determines reachability. 2. Store the gcd in a variable g.

For example:

g = gcd(targetX, targetY)

3. Check whether g is a power of two.

A positive integer is a power of two if and only if:

g & (g - 1) == 0

This works because powers of two contain exactly one set bit in binary form. 4. Return the result of that check.

If the gcd is a power of two, return true.

Otherwise, return false.

Why it works

The crucial invariant is that subtraction operations never change the gcd, and doubling operations can only multiply the gcd by 2.

Since we begin with gcd 1, the only possible gcd values reachable are:

1 * 2^k

for some nonnegative integer k.

Therefore, a target point is reachable if and only if its gcd is a power of two.

This condition is both necessary and sufficient.

Python Solution

from math import gcd

class Solution:
    def isReachable(self, targetX: int, targetY: int) -> bool:
        common_divisor = gcd(targetX, targetY)
        
        return (common_divisor & (common_divisor - 1)) == 0

The implementation is very compact because the mathematical insight eliminates the need for simulation or graph traversal.

First, we import gcd from Python's math module. This computes the greatest common divisor efficiently using the Euclidean algorithm.

Next, we compute:

common_divisor = gcd(targetX, targetY)

This extracts the invariant property that determines reachability.

Finally, we check whether the gcd is a power of two using:

(common_divisor & (common_divisor - 1)) == 0

A power of two has exactly one set bit in binary representation. Subtracting one flips all lower bits, so the bitwise AND becomes zero only for powers of two.

The result of that expression is returned directly.

Go Solution

func isReachable(targetX int, targetY int) bool {
    commonDivisor := gcd(targetX, targetY)

    return (commonDivisor & (commonDivisor - 1)) == 0
}

func gcd(a int, b int) int {
    for b != 0 {
        a, b = b, a%b
    }

    return a
}

The Go version follows the same logic as the Python solution.

Since Go does not provide a built in gcd function for integers in the standard library, we implement the Euclidean algorithm manually.

The bitwise power of two check works identically in Go because integers support bit operations directly.

There are no overflow concerns because the constraints are at most 10^9, which easily fits inside Go's int type on modern platforms.

Worked Examples

Example 1

Input: targetX = 6, targetY = 9

First compute the gcd:

gcd(6, 9) = 3

Now check whether 3 is a power of two.

Binary representation:

3  = 011
2  = 010

Bitwise AND:

3 & 2 = 2

Since the result is not zero, 3 is not a power of two.

Step	Value
targetX	6
targetY	9
gcd	3
Power of two?	No
Result	false

Final answer:

false

Example 2

Input: targetX = 4, targetY = 7

Compute the gcd:

gcd(4, 7) = 1

Now check whether 1 is a power of two.

Binary representation:

1 = 001
0 = 000

Bitwise AND:

1 & 0 = 0

Therefore, 1 is a power of two.

Step	Value
targetX	4
targetY	7
gcd	1
Power of two?	Yes
Result	true

Final answer:

true

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log(min(targetX, targetY)))	Euclidean algorithm complexity
Space	O(1)	Only a few variables are used

The dominant operation is computing the greatest common divisor using the Euclidean algorithm. Each modulo operation significantly reduces the problem size, giving logarithmic complexity.

The algorithm uses constant extra memory because it stores only a few integers regardless of input size.

Test Cases

solution = Solution()

assert solution.isReachable(6, 9) == False   # gcd is 3, not power of two
assert solution.isReachable(4, 7) == True    # gcd is 1

assert solution.isReachable(1, 1) == True    # starting position
assert solution.isReachable(2, 2) == True    # gcd is 2
assert solution.isReachable(4, 4) == True    # gcd is 4
assert solution.isReachable(8, 8) == True    # gcd is 8

assert solution.isReachable(3, 3) == False   # gcd is 3
assert solution.isReachable(5, 10) == False  # gcd is 5
assert solution.isReachable(12, 18) == False # gcd is 6

assert solution.isReachable(1, 1024) == True # large power of two
assert solution.isReachable(1024, 1) == True # asymmetric coordinates

assert solution.isReachable(999999937, 1) == True   # large prime with gcd 1
assert solution.isReachable(1000000000, 500000000) == False  # gcd has odd factor

assert solution.isReachable(536870912, 536870912) == True  # large power of two gcd

Test Case Summary

Test	Why
(6, 9)	gcd contains odd factor
(4, 7)	gcd is 1
(1, 1)	starting point
(2, 2)	smallest nontrivial power of two gcd
(4, 4)	larger power of two gcd
(8, 8)	repeated doubling case
(3, 3)	odd gcd
(5, 10)	gcd is odd prime
(12, 18)	mixed even and odd gcd
(1, 1024)	one coordinate fixed
(1024, 1)	asymmetric case
(999999937, 1)	very large prime coordinate
(1000000000, 500000000)	large invalid gcd
(536870912, 536870912)	very large power of two

Edge Cases

One important edge case is the starting point itself, (1,1). A careless implementation might incorrectly assume some movement is required before success. Here, the gcd is 1, which is a power of two, so the algorithm correctly returns true.

Another important edge case occurs when both coordinates are equal, such as (8,8) or (3,3). In these cases, the gcd equals the coordinate value itself. This makes the result entirely dependent on whether that value is a power of two. The implementation handles this naturally through the gcd check.

A third critical edge case involves very large inputs near the upper constraint limit. A brute force search would fail completely for values near 10^9, either timing out or exhausting memory. The mathematical solution remains efficient because the Euclidean algorithm runs in logarithmic time even for huge numbers.

A subtle edge case occurs when the gcd is even but not a pure power of two, such as 6 or 10. It may initially seem that doubling operations could create such values, but doubling only introduces factors of two. Odd prime factors can never appear after starting from gcd 1. The implementation correctly rejects these cases because the power of two check fails.