Check if Point Is Reachable

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.

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

1import java.util.HashSet;2import java.util.LinkedList;3import java.util.Queue;4import java.util.Set;5 6class Solution {7    // This approach is too slow and will result in Time Limit Exceeded.8    public boolean isReachable(int targetX, int targetY) {9        if (targetX == 1 && targetY == 1) {10            return true;11        }12 13        Queue<long[]> queue = new LinkedList<>();14        queue.add(new long[]{1, 1});15 16        Set<String> visited = new HashSet<>();17        visited.add("1,1");18 19        // Heuristic bound to prevent infinite search, not guaranteed to be correct.20        long boundX = 2L * targetX;21        long boundY = 2L * targetY;22 23        while (!queue.isEmpty()) {24            long[] current = queue.poll();25            long x = current[0];26            long y = current[1];27 28            long[][] nextMoves = {29                {x, y - x},30                {x - y, y},31                {2 * x, y},32                {x, 2 * y}33            };34 35            for (long[] move : nextMoves) {36                long nx = move[0];37                long ny = move[1];38 39                if (nx == targetX && ny == targetY) {40                    return true;41                }42 43                if (nx > 0 && ny > 0 && nx <= boundX && ny <= boundY) {44                    String key = nx + "," + ny;45                    if (!visited.contains(key)) {46                        visited.add(key);47                        queue.add(new long[]{nx, ny});48                    }49                }50            }51        }52 53        return false;54    }55}

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.

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.

1class Solution {2    public boolean isReachable(int targetX, int targetY) {3        // The core idea is that the gcd of any reachable point (x, y) must be a power of 2.4        // This is because we start from (1, 1) with gcd=1. The moves (x, y-x) and (x-y, y)5        // preserve the gcd. The moves (2x, y) and (x, 2y) can at most double the gcd.6        // So, gcd(x, y) must be of the form 2^k.7 8        // First, find the gcd of targetX and targetY.9        int commonDivisor = gcd(targetX, targetY);10 11        // Check if the gcd is a power of 2.12        // A positive integer is a power of 2 if and only if it has only one bit set in its binary representation.13        // The expression (n & (n - 1)) == 0 checks this condition for n > 0.14        return (commonDivisor > 0) && ((commonDivisor & (commonDivisor - 1)) == 0);15    }16 17    // Helper function to compute the greatest common divisor using Euclidean algorithm.18    private int gcd(int a, int b) {19        while (b != 0) {20            int temp = b;21            b = a % b;22            a = temp;23        }24        return a;25    }26}27 28/* Alternative implementation based on the equivalent condition */29class SolutionAlternate {30    public boolean isReachable(int targetX, int targetY) {31        // An equivalent condition for gcd(x,y) being a power of 2 is that32        // the gcd of their odd parts is 1.33        while (targetX % 2 == 0) {34            targetX /= 2;35        }36        while (targetY % 2 == 0) {37            targetY /= 2;38        }39        return gcd(targetX, targetY) == 1;40    }41 42    private int gcd(int a, int b) {43        while (b != 0) {44            int temp = b;45            b = a % b;46            a = temp;47        }48        return a;49    }50}