Introduced during Biweekly Contest 96

Description:

There exists an infinitely large grid. You are currently at a 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:

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.

Difficulty level: Hard

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:

Reasoning:

Solving this problem is difficult as we have a single starting point of (1,1) and different targets for each test case. But if we reverse the direction and try to travel from (x,z) to (1,1), we get a clear scope with a static target destination of (1,1).

Since we have reversed the direction of travel, our traversing operators would also be turned the other way around as shown below:

Now the goal is to decrease x and y until they are both equal to 1. And we have three ways of reducing them: x / 2 and y / 2 for even numbers and (x + y) / 2 when both are odd numbers.

Let’s simulate the positive scenario when it’s possible.

As shown in the picture above, if x = 2^m and starting point is(2^m, y), we can keep dividing the first number by two(2^m / 2) until it reaches (1, y). Then we can keep incrementing y by one(y + 1) until it reaches (1, 2^n).

From here, we can again keep dividing the other number by two (2^n / 2) until it reaches the final(1, 1) point. Using the same operations, we can travel from (x, 2^n) to (1, 1).

Now, we can conclude that we can get to the target if one of the numbers/coordinates becomes a power of two (2^m).

Now, let's find the scenario when it’s not possible to reach the target of (1,1). We know that we can always decrease x / 2 and y / 2 for even numbers and (x + y) / 2 when both are odd numbers.

This means the number can always go smaller except in one scenario, when x and y are equal (x = y) and both are odd numbers (x % 2 <> 0). For example, (3, 3), (5, 5) , etc. That is the situation when we are stuck and cannot decrease coordinates (x and y) anymore.

But how do we get there?

Assuming that both x and y have a common divisor d ( x % d === 0 and y % d === 0). If so, their sum (x + y) will also have the same common divisor d ( (x + y) % d === 0 ). Suppose that a common divisor is a prime number that is greater than two, for example, it’s equal to 3 (d = 3).

That means x = 3a y = 3b & (x + y) = 3(a + b) where a and b are some integers. No matter what the a and b , we can’t divide either one by 2 often enough to end up with 1 because the 3 always get in the way.

If x and y both have a prime factor of d (3, 5, 7, 11, etc.), then any number of addition or division operations performed in any order will leave both numbers with a common factor of d (3, 5, 7, 11, etc.).

So we can safely conclude that if x and y have any common prime factor other than 2, then reaching the final point of (1,1) is not possible.

We can find all common prime factors of x and y, and check if any of those is not equal to 2.

Or even more accessible, determine the Greatest Common Divisor — GCD (which is the multiplication of all common prime factors) and if it is a power of 2 (GCD === 2^k), then all our common prime factors are equal to 2.

In opposite cases, for example, if GCD is equal to 20, the common prime factors would be 2, 2 & 5 (20 = 2 * 2 * 5), and that nasty 5 wouldn’t allow us to reach our target destination of (1, 1).

To conclude, if and only if the Greatest Common Divisor of x and y is a power of 2 (GCD === 2^k and k ≥ 0), then it is possible to reach the target.

Solution:

First of all, we need to implement a function for determining the Greatest Common Divisor of two numbers. There are many ways of doing that; in our case, we will use the Euclidean Algorithm because of conciseness and efficiency.

You can read more about the JS implementation of the algorithm here.

function gcd(x, y){
    if (y===0)
        return x;
    return gcd(y, x%y);
}

Next, we need to determine if GCD is a power of two. One way of doing that is to keep dividing by 2 until it becomes 1 or another prime number. And that solution is sufficient for passing all of the LeetCode with competitive performance. So the final JS code would look like one below:

function gcd(x, y){
    if (y===0)
        return x;
    return gcd(y, x%y);
}
var isReachable = function(targetX, targetY) {
    let gc = gcd(targetX,targetY);
    while (gc % 2 ===0) {
       gc /= 2
    }
    return gc === 1
};

Bitwise Solution:

Another way is to use the bitwise operator AND. Converting 2^k to binary would give us one followed by k zeros (for example 2³ => 1000), and the representation of 2^k-1 in binary would be k times one (for example, 2³-1 => 111), as shown in the picture below.

And if we perform AND operator for each of the pairs, the result would always be equal to zero (2^k & 2^k-1 = 0) as shown in the picture below.

So the final code for the solution that uses the bitwise AND operator would look like the one below.

function gcd(x, y){
    if (y===0)
        return x;
    return gcd(y, x%y);
}
var isReachable = function(targetX, targetY) {
    let gc = gcd(targetX,targetY);
    return (gc&(gc-1))==0;
};

The code above beats 100% of all JS submissions in terms of performance and is very optimal in terms of memory usage. Time complexity is O(log(min(x,y))) and space complexity of O(log(min(x,y))).

Also published here