Skip to content

2543. Check if Point Is Reachable 👍

  • Time: $O(\log\texttt{targetX} + \log\texttt{targetY})$
  • Space: $O(1)$
1
2
3
4
5
6
class Solution {
 public:
  bool isReachable(unsigned targetX, unsigned targetY) {
    return popcount(gcd(targetX, targetY)) == 1;
  }
};

1
2
3
4
5
6
7
8
9
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);
  }
}

1
2
3
class Solution:
  def isReachable(self, targetX: int, targetY: int) -> bool:
    return math.gcd(targetX, targetY).bit_count() == 1