How to Check If Your Point Is Reachable: A JavaScript Algorithms Guideby@kzarman

# How to Check If Your Point Is Reachable: A JavaScript Algorithms Guide

March 22nd, 2023

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 this short article, I’ll explain the reasoning and provide the solution written in JavaScript.

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:

• `(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`

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

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

## 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

L O A D I N G
. . . comments & more!