2543. Check if Point Is Reachable

HardMathNumber Theory

Problem Description

The problem presents an infinite grid where you start at the coordinates (1, 1) and your goal is to reach a target point (targetX, targetY) through a series of steps. At each step, you are allowed to move to a new point by either doubling the x or y coordinate, or subtracting the value of y from x, or the value of x from y. The task is to determine if it is possible to reach the target using a finite number of these operations. You need to return true if the target can be reached, or false if it is impossible.

Intuition

The key to solving this problem lies in recognizing that the operations can be performed in a reversible manner, implying that starting from the target point (targetX, targetY) and working our way back to (1, 1) is equivalent to moving from (1, 1) to (targetX, targetY). In particular, because the subtract operations could potentially make coordinates negative (which is not allowed in the problem), we realize that the only way to reach (targetX, targetY) without ever being in the negatives is if both targetX and targetY have a common factor that is a power of 2.

The solution, therefore, is to calculate the greatest common divisor (GCD) of targetX and targetY. If their GCD is a power of 2, it would mean that we can scale down both coordinates by dividing by the GCD and eventually reach (1, 1) without encountering any issues with negative numbers.

To check if the GCD is indeed a power of 2, we use the bit manipulation approach: a number n is a power of 2 if and only if n & (n - 1) == 0 where & is the bitwise AND operator. This condition checks whether n has exactly one non-zero bit, which is the characteristic property of powers of 2.

The insight that the path can be traced backwards efficiently is crucial, as trying to simulate all potential forward paths would be impractical given the size of the grid and the number of steps potentially involved.

Learn more about Math patterns.

Solution Approach

The solution leverages a mathematical approach rather than a step-by-step simulation, which would be computationally intensive. This approach uses both number theory and bit manipulation to solve the problem. Here's a step-by-step breakdown of the algorithm implemented in the provided solution:

The solution begins by invoking the gcd function from Python's [math](/problems/math-basics) module to calculate the Greatest Common Divisor (GCD) of targetX and targetY. The function gcd takes two integers and returns their largest common factor. In mathematical terms, x = gcd(targetX, targetY).
After calculating the GCD, the solution checks if x is a power of two. This is accomplished using a bit manipulation trick: x & (x - 1) == 0. In this expression, the bitwise AND operator & is used between the number x and the number x - 1.
- If x is a power of two, it means it has a binary representation with only a single 1 bit set, and all other bits set to 0.
- The expression x - 1 converts the rightmost 1 bit of x to 0 and flips all the bits to the right of it. For example, if x is 8 (binary 1000), then x - 1 is 7 (binary 0111).
- When you perform the bitwise AND of x with x - 1, if x is a power of two, the result will be 0 because there are no overlapping 1 bits in the two numbers.
The final step is to return whether the GCD is a power of two using the result of the bit manipulation check. If the check passes, the function returns True, indicating the target point (targetX, targetY) is reachable. Otherwise, it returns False.

By explicating the approach in terms of number theory (GCD) and optimizing with bit manipulation, the solution circumvents the need for complex data structures or algorithms. It elegantly exploits the properties of numbers and operations allowed to deduce the reachability of the target coordinates.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach using a small example where the target coordinate is (12, 8). Our task is to determine if it is possible to reach this target coordinate (12, 8) from the starting coordinate (1, 1) by either doubling the x or y coordinate or by subtracting the value of y from x or the value of x from y.

Calculating the GCD: First, we find the GCD of the target coordinates ( targetX = 12 ) and ( targetY = 8 ). Using Python's math.gcd() function, we find that the GCD of 12 and 8 is 4.
Checking if the GCD is a power of 2: Our next step is to check if the GCD (which is 4 in this case) is a power of 2. To perform this check, we use the expression gcd & (gcd - 1) == 0.
- For our GCD, 4, we calculate 4 & (4 - 1) which is 4 & 3.
- In binary form, 4 is 100 and 3 is 011. The bitwise AND of 100 & 011 results in 000, which is 0.
Returning the result: Since the calculation from the previous step gives us 0, it confirms that our GCD, 4, is indeed a power of 2. Thus, according to our algorithm, this implies that the target coordinate (12, 8) can be reached from (1, 1).

Following these steps, the final output for our example is True, which means the movement from (1, 1) to (12, 8) is possible with a finite number of the described operations.

Solution Implementation

1from math import gcd  # Import the gcd function from the math module
2
3class Solution:
4    def isReachable(self, target_x: int, target_y: int) -> bool:
5        # Calculate the greatest common divisor (GCD) of target_x and target_y
6        greatest_common_divisor = gcd(target_x, target_y)
7      
8        # Check if the GCD is a power of two
9        # A number is a power of two if it's bitwise 'and' with itself minus one is zero
10        return greatest_common_divisor & (greatest_common_divisor - 1) == 0
11

1class Solution {
2    // Method to check if the point (targetX, targetY) is reachable
3    public boolean isReachable(int targetX, int targetY) {
4        // Calculate the greatest common divisor (GCD) of targetX and targetY
5        int gcdValue = gcd(targetX, targetY);
6
7        // Check if gcdValue is a power of 2 by using bitwise AND with gcdValue - 1
8        // If the result is 0, then gcdValue is indeed a power of 2
9        return (gcdValue & (gcdValue - 1)) == 0;
10    }
11
12    // Helper method to calculate the greatest common divisor (GCD) of two numbers using recursion
13    private int gcd(int number1, int number2) {
14        // If number2 is 0, return number1 as the GCD
15        if (number2 == 0) {
16            return number1;
17        }
18        // Recur with number2 and the remainder of number1 divided by number2
19        return gcd(number2, number1 % number2);
20    }
21}
22

1#include <algorithm> // Include the algorithm header for the 'std::gcd' function
2
3class Solution {
4public:
5    // Function to check if a point (targetX, targetY) is reachable
6    // The point is reachable if the greatest common divisor of X and Y is a power of 2
7    bool isReachable(int targetX, int targetY) {
8        // Finding the greatest common divisor (GCD) of targetX and targetY
9        int gcdValue = std::gcd(targetX, targetY);
10      
11        // Check if gcdValue is a power of 2 by using the property:
12        // A number n is a power of 2 if and only if n & (n - 1) is 0,
13        // where & is the bitwise AND operator.
14        // This works because a power of 2 has only one bit set in its binary representation,
15        // and (n - 1) would have all the bits set before that particular bit.
16        return (gcdValue & (gcdValue - 1)) == 0;
17    }
18};
19

1// Calculate the greatest common divisor (GCD) of two numbers
2function gcd(a: number, b: number): number {
3    // Base case: if b is 0, a is the gcd
4    if (b === 0) {
5        return a;
6    }
7    // Recursive case: call gcd with b and the remainder of a divided by b
8    return gcd(b, a % b);
9}
10
11// Determine if the location (targetX, targetY) is reachable
12function isReachable(targetX: number, targetY: number): boolean {
13    // Find the gcd of the target coordinates
14    const greatestCommonDivisor = gcd(targetX, targetY);
15  
16    // Check if the gcd is a power of two (i.e., has only one '1' bit in binary)
17    // This is done by performing the binary AND operation between x and (x - 1)
18    // If the result is zero, then x is a power of two
19    // This step is crucial because being able to reach a position (x, y) on a 
20    // number line using moves that double the number at each step is only possible
21    // when the gcd of (x, y) is a power of two
22    return (greatestCommonDivisor & (greatestCommonDivisor - 1)) === 0;
23}
24

Time and Space Complexity

The time complexity of the code is O(log(min(targetX, targetY))), driven by the gcd function which performs a series of modulus operations until it finds the greatest common divisor of targetX and targetY. This process takes a time proportional to the logarithm of the smaller of the two inputs.

The space complexity of the code is O(1) since it uses only a constant amount of additional memory. The gcd function stores intermediate values, but these do not scale with the input size and are instead limited to a fixed number of simple variables necessary for the computation.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27

1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30

1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

["jk", "mno"]

["jm", "kn", "lo"]

["jklmnp"]

["jm","jn","jo","km","kn","ko","lm","ln","lo"]

I don’t know