paint-brush
How to Check If Your Point Is Reachable: A JavaScript Algorithms Guideby@kzarman
244 reads

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

by Arman MurzabulatovMarch 22nd, 2023
Read on Terminal Reader
Read this story w/o Javascript
tldt arrow

Too Long; Didn't Read

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.
featured image - How to Check If Your Point Is Reachable: A JavaScript Algorithms Guide
Arman Murzabulatov HackerNoon profile picture


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


Runtime and memory usage by LeetCode


Also published here