What is the time complexity of Check if Point Is Reachable?

The optimal solution has a time complexity of O(log(min(x, y))).

What data structures are used to solve Check if Point Is Reachable?

This problem uses Math, Number Theory. Understanding these concepts is essential for solving this Hard problem efficiently.

What are the key insights for solving Check if Point Is Reachable?

Insight 1: The greatest common divisor (GCD) plays a crucial role in determining reachability. Operations (x, y-x) and (x-y, y) preserve the GCD. Operations (2x, y) and (x, 2y) can at most multiply the GCD by 2. Insight 2: Starting from (1, 1), the GCD is 1. Any reachable point (targetX, targetY) must have a GCD that is a power of 2.

Which companies ask LeetCode 2543. Check if Point Is Reachable in interviews?

This problem is frequently asked at PhonePe.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Check if Point Is Reachable - LeetCode 2543 Solution

Q: How to solve Check if Point Is Reachable?

The solution leverages the properties of the GCD under the allowed moves. The core idea is that if a point (targetX, targetY) is reachable from (1, 1), then their greatest common divisor (GCD) must be a power of 2. This is because the initial GCD is 1, and each operation either preserves the GCD or multiplies it by 2. The solution calculates the GCD of targetX and targetY and then checks if the GCD is a power of 2 using a bitwise operation (g & (g - 1)) == 0. If it is, the target is reachable; otherwise, it is not.

Check if Point Is Reachable - Complete Solution Guide

Check if Point Is Reachable is LeetCode problem 2543, a Hard level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

There exists an infinitely large grid. You are currently at 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 . Exampl

Detailed Explanation

The problem asks whether a point (targetX, targetY) is reachable from (1, 1) on an infinite grid. The allowed moves are (x, y) -> (x, y - x), (x, y) -> (x - y, y), (x, y) -> (2 * x, y), and (x, y) -> (x, 2 * y). We need to return `true` if the target is reachable, and `false` otherwise. The constraints are 1 <= targetX, targetY <= 10^9.

Solution Approach

The solution leverages the properties of the GCD under the allowed moves. The core idea is that if a point (targetX, targetY) is reachable from (1, 1), then their greatest common divisor (GCD) must be a power of 2. This is because the initial GCD is 1, and each operation either preserves the GCD or multiplies it by 2. The solution calculates the GCD of targetX and targetY and then checks if the GCD is a power of 2 using a bitwise operation (g & (g - 1)) == 0. If it is, the target is reachable; otherwise, it is not.

Step-by-Step Algorithm

Step 1: Calculate the greatest common divisor (GCD) of targetX and targetY using the Euclidean algorithm.
Step 2: Check if the calculated GCD is a power of 2. This is done efficiently by checking if (GCD & (GCD - 1)) == 0. If the result is 0, then the GCD is a power of 2.
Step 3: Return true if the GCD is a power of 2; otherwise, return false.

Key Insights

Insight 1: The greatest common divisor (GCD) plays a crucial role in determining reachability. Operations (x, y-x) and (x-y, y) preserve the GCD. Operations (2x, y) and (x, 2y) can at most multiply the GCD by 2.
Insight 2: Starting from (1, 1), the GCD is 1. Any reachable point (targetX, targetY) must have a GCD that is a power of 2.
Insight 3: The reverse operations (x, y+x), (x+y, y), (x/2, y), and (x, y/2) are also important for understanding the problem. The greatest odd divisor of the GCD is an invariant when applying these reverse operations. Since gcd_odd(1, 1) is 1, any reachable point must also have a gcd with greatest odd divisor of 1, implying the GCD is a power of 2.
Insight 4: A number is a power of 2 if and only if (n & (n - 1)) == 0, making it an efficient way to check the result.

Complexity Analysis

Time Complexity: O(log(min(x, y)))

Space Complexity: O(1)

Topics

This problem involves: Math, Number Theory.

Companies

Asked at: PhonePe.

Check if Point Is Reachable | LeetCode 2543

Hard

Math Number Theory

Time: O(log(min(x, y)))Space: O(1)

Solution Code

Available in:

class Solution {
    public boolean isReachable(int targetX, int targetY) {
        // The greatest common divisor (GCD) of the coordinates changes in a specific way.
        // Let g = gcd(x, y).
        // Moves (x, y-x) and (x-y, y) preserve the GCD: gcd(x, y-x) = g, gcd(x-y, y) = g.
        // Moves (2*x, y) and (x, 2*y) can change the GCD to g or 2*g.
        // Starting from (1, 1), where gcd is 1, any reachable point (tx, ty)
        // must have gcd(tx, ty) as a power of 2.

        // We need to show this is also a sufficient condition.
        // This can be done by considering the path in reverse, from (targetX, targetY) to (1, 1).
        // The inverse moves are (x, y+x), (x+y, y), (x/2, y), (x, y/2).
        // The greatest odd divisor of the GCD is an invariant under these inverse operations.
        // If (targetX, targetY) can reach (1, 1), then their greatest odd divisors of GCDs must be the same.
        // gcd_odd(1, 1) is 1. So, gcd_odd(targetX, targetY) must be 1.
        // This implies gcd(targetX, targetY) must be a power of 2.
        
        // A reduction argument shows that if gcd(targetX, targetY) is a power of 2,
        // we can always find a sequence of inverse moves to reach (1, 1).

        int g = gcd(targetX, targetY);
        
        // A positive integer is a power of 2 if and only if it has only one bit set in its binary representation.
        // This can be checked with the bitwise trick: (g & (g - 1)) == 0.
        return (g & (g - 1)) == 0;
    }

    private int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 2543: Check if Point Is Reachable - Detailed explanation and solution approaches.

Topics

Math Number Theory

Companies

PhonePe

Stats

Difficulty:Hard

Languages:4

Companies:1

Problem #:2543

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

3 steps

1
Step 1: Calculate the greatest common divisor (GCD) of targetX and targetY using the Euclidean algorithm.
2
Step 2: Check if the calculated GCD is a power of 2. This is done efficiently by checking if (GCD & (GCD - 1)) == 0. If the result is 0, then the GCD is a power of 2.
3
Step 3: Return true if the GCD is a power of 2; otherwise, return false.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(log(min(x, y)))

🚀 Logarithmic - Very efficient! Halves the problem each step.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The time complexity is dominated by the Euclidean algorithm for calculating the GCD, which takes O(log(min(targetX, targetY))) time. The bitwise operation takes constant time, so it doesn't affect the overall time complexity. The space complexity is O(1) because we only use a few constant space variables.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Iterative Subtraction-Based GCD

Instead of using the modulo operator in the Euclidean algorithm, we can repeatedly subtract the smaller number from the larger one until they are equal. The equal value will be the GCD.

Time: O(max(targetX, targetY)) in worst case, close to O(log(min(targetX, targetY))) on averageSpace: O(1)

Trade-offs: This approach is simpler to implement but can be slower than the standard Euclidean algorithm, especially when the two numbers have significantly different magnitudes.

✨

Key Insights

1Insight 1: The greatest common divisor (GCD) plays a crucial role in determining reachability. Operations (x, y-x) and (x-y, y) preserve the GCD. Operations (2x, y) and (x, 2y) can at most multiply the GCD by 2.
2Insight 2: Starting from (1, 1), the GCD is 1. Any reachable point (targetX, targetY) must have a GCD that is a power of 2.
3Insight 3: The reverse operations (x, y+x), (x+y, y), (x/2, y), and (x, y/2) are also important for understanding the problem. The greatest odd divisor of the GCD is an invariant when applying these reverse operations. Since gcd_odd(1, 1) is 1, any reachable point must also have a gcd with greatest odd divisor of 1, implying the GCD is a power of 2.
4Insight 4: A number is a power of 2 if and only if (n & (n - 1)) == 0, making it an efficient way to check the result.

📚

Key Terms Explained

For Students

Edge Cases

Edge case 1: targetX = 1, targetY = 1. The GCD is 1, which is a power of 2 (2^0). The solution correctly returns true.
Edge case 2: targetX = 2, targetY = 4. The GCD is 2, which is a power of 2. The solution correctly returns true.
Edge case 3: targetX = 6, targetY = 9. The GCD is 3, which is not a power of 2. The solution correctly returns false.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting to handle the base case where the GCD is 1. 1 is a power of 2 (2^0), so it should return true.

✗Common mistake 2: Incorrectly implementing the GCD algorithm, leading to wrong GCD values and, consequently, incorrect results.

✗Common mistake 3: Confusing the bitwise check for a power of 2. Ensure the expression `(g & (g - 1)) == 0` is used correctly.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Cryptography - GCD calculations are fundamental in many cryptographic algorithms, such as RSA, for key generation and modular arithmetic.

🏦Real-world scenario 2: Resource allocation - GCD can be used to divide resources (e.g., tasks, memory) evenly among multiple users or processes.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

These problems test your ability to optimize. Start with a brute force solution, then improve.

⚠️ Watch Out

Always test your solution with edge cases: empty input, single element, and boundary values.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: June 24, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 13

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 6

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jun 29

❓

Frequently Asked Questions

Is it okay to not fully solve hard problems in interviews?

Yes! Interviewers care more about your problem-solving process than the final answer. Demonstrate: clear communication, systematic approach, ability to recognize when to pivot strategies, and graceful handling of hints. Partial progress with good reasoning is valued.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Check if Point Is Reachable"?

For this hard-level Math problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether number theory techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?