# Check if Point Is Reachable
**Difficulty:** HARD
[External](https://leetcode.com/problems/check-if-point-is-reachable)
Canonical: https://scaleengineer.com/dsa/problems/check-if-point-is-reachable
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Companies:** [PhonePe](https://scaleengineer.com/companies/phonepe)
---
## Problem
There exists an infinitely large grid. You are currently at point `(1, 1)`, and you need to reach the point `(targetX, targetY)` using a finite number of steps.

In one **step**, you can move from point `(x, y)` to any one of the following points:

* `(x, y - x)`
* `(x - y, y)`
* `(2 * x, y)`
* `(x, 2 * y)`

Given two integers `targetX` and `targetY` representing the X-coordinate and Y-coordinate of your final position, return `true` _if you can reach the point from_ `(1, 1)` _using some number of steps, and_ `false` _otherwise_.

**Example 1:**

**Input:** targetX = 6, targetY = 9
**Output:** false
**Explanation:** It is impossible to reach (6,9) from (1,1) using any sequence of moves, so false is returned.

**Example 2:**

**Input:** targetX = 4, targetY = 7
**Output:** true
**Explanation:** You can follow the path (1,1) -> (1,2) -> (1,4) -> (1,8) -> (1,7) -> (2,7) -> (4,7).

**Constraints:**

* `1 <= targetX, targetY <= 109`

# Approaches
## Brute-force Breadth-First Search (BFS)
A straightforward but inefficient approach is to treat the problem as a graph traversal problem. The grid points are the nodes of the graph, and the allowed moves are the directed edges. We can start a Breadth-First Search (BFS) from the initial point `(1, 1)` and explore all reachable points.
**Time:** O(V + E), where V (vertices) and E (edges) are related to the size of the search space. This is exponential in the magnitude of the target coordinates and will not pass. · **Space:** O(targetX * targetY) or larger, depending on the bounds. This is infeasible for the given constraints.
**Pros:** Conceptually simple and easy to understand for graph traversal problems.
**Cons:** Extremely high time complexity, leading to Time Limit Exceeded (TLE) for the given constraints.; Very high space complexity due to the need to store a large number of visited states.; It's difficult to establish correct bounds for the search space. Coordinates might need to become larger than the target before they can be reduced to the target values.
### Explanation
We can use a queue to manage the points to visit and a set to keep track of visited points to avoid cycles and redundant computations. The search begins with `(1, 1)`. In each step, we take a point from the queue, check if it's the target, and if not, we generate all possible next points using the four allowed moves. These new, unvisited points are then added to the queue. 

However, the coordinates can grow very large, potentially leading to an infinite search space. To make this feasible, we would need to prune the search space by setting some upper bounds on the coordinates. For instance, we might guess that we don't need to explore points with coordinates much larger than the target's. This heuristic is hard to prove correct and, even with it, the number of states to visit is enormous given that `targetX` and `targetY` can be up to 10<sup>9</sup>.

```java
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

class Solution {
    // This approach is too slow and will result in Time Limit Exceeded.
    public boolean isReachable(int targetX, int targetY) {
        if (targetX == 1 && targetY == 1) {
            return true;
        }

        Queue<long[]> queue = new LinkedList<>();
        queue.add(new long[]{1, 1});

        Set<String> visited = new HashSet<>();
        visited.add("1,1");

        // Heuristic bound to prevent infinite search, not guaranteed to be correct.
        long boundX = 2L * targetX;
        long boundY = 2L * targetY;

        while (!queue.isEmpty()) {
            long[] current = queue.poll();
            long x = current[0];
            long y = current[1];

            long[][] nextMoves = {
                {x, y - x},
                {x - y, y},
                {2 * x, y},
                {x, 2 * y}
            };

            for (long[] move : nextMoves) {
                long nx = move[0];
                long ny = move[1];

                if (nx == targetX && ny == targetY) {
                    return true;
                }

                if (nx > 0 && ny > 0 && nx <= boundX && ny <= boundY) {
                    String key = nx + "," + ny;
                    if (!visited.contains(key)) {
                        visited.add(key);
                        queue.add(new long[]{nx, ny});
                    }
                }
            }
        }

        return false;
    }
}
```
### Algorithm
1. Create a queue and add the starting point `(1, 1)`.
2. Create a `visited` set to store points that have already been explored, and add `(1, 1)` to it.
3. While the queue is not empty, dequeue a point `(x, y)`.
4. If `(x, y)` is the target `(targetX, targetY)`, return `true`.
5. Generate all possible next points from `(x, y)`:
   - `(x, y - x)`
   - `(x - y, y)`
   - `(2 * x, y)`
   - `(x, 2 * y)`
6. For each new point `(nx, ny)`:
   - Check if the point is valid (e.g., coordinates are positive).
   - To prevent the search from running indefinitely, apply some bounds, for example, `nx <= 2 * targetX` and `ny <= 2 * targetY`. This is a heuristic and may not be correct for all cases.
   - If the point has not been visited, add it to the queue and the `visited` set.
7. If the queue becomes empty and the target has not been found, it means the target is unreachable. Return `false`.

## Mathematical Approach using Greatest Common Divisor (GCD)
A highly efficient solution can be derived by analyzing the properties of the numbers involved, specifically their greatest common divisor (GCD). The key idea is to observe how the GCD of the coordinates `(x, y)` changes with each move.
**Time:** O(log(min(targetX, targetY))). The Euclidean algorithm's complexity is logarithmic in the value of the smaller input. · **Space:** O(1) if using an iterative GCD algorithm. O(log(min(targetX, targetY))) if using a recursive GCD algorithm due to call stack depth.
**Pros:** Extremely efficient, with logarithmic time complexity.; Constant space complexity (for iterative GCD).; Provides a definitive answer without any heuristics.
**Cons:** The solution relies on a non-trivial insight from number theory, which can be difficult to come up with during a contest.
### Explanation
Let's analyze the moves:
- `(x, y - x)` and `(x - y, y)`: These are the subtraction steps of the Euclidean algorithm. They do not change the GCD of the coordinates, i.e., `gcd(x, y) = gcd(x, y - x)`. 
- `(2 * x, y)` and `(x, 2 * y)`: These doubling moves can affect the GCD. The `gcd(2x, y)` will be either `gcd(x, y)` or `2 * gcd(x, y)`. 

We start at `(1, 1)`, where `gcd(1, 1) = 1 = 2^0`. Since the subtraction moves preserve the GCD and the doubling moves can only introduce factors of 2 into the GCD, any point `(x, y)` reachable from `(1, 1)` must have a GCD that is a power of 2. This gives us a necessary condition: if `gcd(targetX, targetY)` is not a power of 2, the point is unreachable.

This condition turns out to be sufficient as well. We can show that any point `(x, y)` where `gcd(x, y)` is a power of 2 is reachable. A simpler way to check if `gcd(targetX, targetY)` is a power of 2 is to first remove all factors of 2 from both `targetX` and `targetY`. Let the resulting odd numbers be `x_odd` and `y_odd`. Then `gcd(targetX, targetY)` is a power of 2 if and only if `gcd(x_odd, y_odd) = 1`.

So, the algorithm simplifies to: divide `targetX` and `targetY` by 2 until they become odd, then check if their GCD is 1.

```java
class Solution {
    public boolean isReachable(int targetX, int targetY) {
        // The core idea is that the gcd of any reachable point (x, y) must be a power of 2.
        // This is because we start from (1, 1) with gcd=1. The moves (x, y-x) and (x-y, y)
        // preserve the gcd. The moves (2x, y) and (x, 2y) can at most double the gcd.
        // So, gcd(x, y) must be of the form 2^k.

        // First, find the gcd of targetX and targetY.
        int commonDivisor = gcd(targetX, targetY);

        // Check if the gcd is a power of 2.
        // A positive integer is a power of 2 if and only if it has only one bit set in its binary representation.
        // The expression (n & (n - 1)) == 0 checks this condition for n > 0.
        return (commonDivisor > 0) && ((commonDivisor & (commonDivisor - 1)) == 0);
    }

    // Helper function to compute the greatest common divisor using Euclidean algorithm.
    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

/* Alternative implementation based on the equivalent condition */
class SolutionAlternate {
    public boolean isReachable(int targetX, int targetY) {
        // An equivalent condition for gcd(x,y) being a power of 2 is that
        // the gcd of their odd parts is 1.
        while (targetX % 2 == 0) {
            targetX /= 2;
        }
        while (targetY % 2 == 0) {
            targetY /= 2;
        }
        return gcd(targetX, targetY) == 1;
    }

    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}
```
### Algorithm
1. Analyze the effect of each move on the greatest common divisor (GCD) of the coordinates `(x, y)`.
2. The moves `(x, y - x)` and `(x - y, y)` are steps in the Euclidean algorithm and preserve the GCD: `gcd(x, y) = gcd(x, y - x) = gcd(x - y, y)`.
3. The moves `(2 * x, y)` and `(x, 2 * y)` can change the GCD. `gcd(2x, y)` is either `gcd(x, y)` or `2 * gcd(x, y)`.
4. Since we start at `(1, 1)` where `gcd(1, 1) = 1`, any reachable point `(x, y)` must have a GCD that is a power of 2. This is a necessary condition.
5. This condition is also sufficient. Any point `(x, y)` where `gcd(x, y) = 2^k` for some `k >= 0` is reachable.
6. To prove sufficiency, we show that any coprime pair `(a, b)` is reachable from `(1, 1)` using the reverse of the Euclidean algorithm steps. Then, from `(a, b)`, we can reach `(2^i * a, 2^j * b)` using the doubling moves. Any `(targetX, targetY)` where `gcd(targetX, targetY)` is a power of 2 can be constructed this way.
7. An equivalent and simpler check is to remove all factors of 2 from `targetX` and `targetY` to get their odd parts, let's call them `x_odd` and `y_odd`. The original `gcd(targetX, targetY)` is a power of 2 if and only if `gcd(x_odd, y_odd) = 1`.
8. The final algorithm is:
   a. Remove all factors of 2 from `targetX`.
   b. Remove all factors of 2 from `targetY`.
   c. Check if the resulting numbers are coprime using the GCD algorithm. If `gcd` is 1, return `true`, otherwise `false`.

# Solutions
### Java

```java
class Solution {
public
  boolean isReachable(int targetX, int targetY) {
    int x = gcd(targetX, targetY);
    return (x & (x - 1)) == 0;
  }
private
  int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
}

```

### CPP

```cpp
class Solution {
public:
  bool isReachable(int targetX, int targetY) {
    int x = gcd(targetX, targetY);
    return (x & (x - 1)) == 0;
  }
};

```

### Python

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

```