Introduced during Biweekly Contest 96 Description: There exists an infinitely large grid. You are currently at a point , and you need to reach the point using a finite number of steps. (1, 1) (targetX, targetY) In one , you can move from point to any one of the following points: step (x, y) (x, y - x) (x - y, y) (2 * x, y) (x, 2 * y) Given two integers and representing the X-coordinate and Y-coordinate of your final position, return . targetX targetY 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 and different targets for each test case. But if we reverse the direction and try to travel from to , we get a clear scope with a static target destination of . (1,1) (x,z) (1,1) (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) if (x / 2, y) x % 2 == 0 if (x, y / 2) y % 2 == 0 Now the goal is to decrease and until they are both equal to 1. And we have three ways of reducing them: and for even numbers and when both are odd numbers. x y x / 2 y / 2 (x + y) / 2 Let’s simulate the positive scenario when it’s possible. As shown in the picture above, if and starting point is , we can keep dividing the first number by two until it reaches . Then we can keep incrementing by one until it reaches . x = 2^m (2^m, y) (2^m / 2) (1, y) y (y + 1) (1, 2^n) From here, we can again keep dividing the other number by two until it reaches the final point. Using the same operations, we can travel from to . (2^n / 2) (1, 1) (x, 2^n) (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 . We know that we can always decrease and for even numbers and when both are odd numbers. (1,1) x / 2 y / 2 (x + y) / 2 This means the number can always go smaller except in one scenario, when and are equal ( ) and both are odd numbers ( ). For example, , , etc. That is the situation when we are stuck and cannot decrease coordinates ( and ) anymore. x y x = y x % 2 <> 0 (3, 3) (5, 5) x y But how do we get there? Assuming that both and have a common divisor ( and ). If so, their sum will also have the same common divisor ( ). Suppose that a common divisor is a prime number that is greater than two, for example, it’s equal to 3 ( ). x y d x % d === 0 y % d === 0 (x + y) d (x + y) % d === 0 d = 3 That means & where and are some integers. No matter what the and , we can’t divide either one by 2 often enough to end up with 1 because the 3 always get in the way. x = 3a y = 3b (x + y) = 3(a + b) a b a b If and both have a prime factor of (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 (3, 5, 7, 11, etc.). x y d d So we can safely conclude that if x and have any common prime factor other than 2, then reaching the final point of is not possible. y (1,1) We can find all common prime factors of and , and check if any of those is not equal to 2. x y 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 ( ), then all our common prime factors are equal to 2. GCD === 2^k 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 ( ), then it is possible to reach the target. GCD === 2^k and k ≥ 0 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 to binary would give us one followed by zeros (for example 2³ => 1000), and the representation of in binary would be times one (for example, 2³-1 => 111), as shown in the picture below. 2^k k 2^k-1 k And if we perform AND operator for each of the pairs, the result would always be equal to zero ( ) as shown in the picture below. 2^k & 2^k-1 = 0 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 and space complexity of . O(log(min(x,y))) O(log(min(x,y))) Also published here

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

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

A Guide to Angular Signals With Practical Use Cases (Part 1)

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

The Noonification: How to Develop a DSL in Kotlin (12/12/2023)

A Guide to Angular Signals With Practical Use Cases (Part 1)

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

The Noonification: How to Develop a DSL in Kotlin (12/12/2023)

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps