2543. Check if Point Is Reachable LeetCode Solution

In this guide, you will get 2543. Check if Point Is Reachable LeetCode Solution with the best time and space complexity. The solution to Check if Point Is Reachable problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Check if Point Is Reachable solution in C++
  4. Check if Point Is Reachable solution in Java
  5. Check if Point Is Reachable solution in Python
  6. Additional Resources
2543. Check if Point Is Reachable LeetCode Solution image

Problem Statement of Check if Point Is Reachable

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.

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

See also  3146. Permutation Difference between Two Strings LeetCode Solution

Constraints:

1 <= targetX, targetY <= 109

Complexity Analysis

  • Time Complexity: O(\log\texttt{targetX} + \log\texttt{targetY})
  • Space Complexity: O(1)

2543. Check if Point Is Reachable LeetCode Solution in C++

class Solution {
 public:
  bool isReachable(unsigned targetX, unsigned targetY) {
    return popcount(gcd(targetX, targetY)) == 1;
  }
};
/* code provided by PROGIEZ */

2543. Check if Point Is Reachable LeetCode Solution in Java

class Solution {
  public boolean isReachable(int targetX, int targetY) {
    return Integer.bitCount(gcd(targetX, targetY)) == 1;
  }

  private int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
  }
}
// code provided by PROGIEZ

2543. Check if Point Is Reachable LeetCode Solution in Python

class Solution:
  def isReachable(self, targetX: int, targetY: int) -> bool:
    return math.gcd(targetX, targetY).bit_count() == 1
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Similar: