**NODES, The Dev Community Conference by Neo4j!**

244 reads

by Arman MurzabulatovMarch 22nd, 2023

Introduced during Biweekly Contest 96

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:

`(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*.

*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:**

`1 <= targetX, targetY <= 109`

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:

`(x, y + x)`

`(x + y, y)`

`(x / 2, y)`

if`x % 2 == 0`

`(x, y / 2)`

if`y % 2 == 0`

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.

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

```
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
};
```

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*

L O A D I N G

. . . comments & more!

. . . comments & more!