We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Check if Point Is Reachable

Number: 2635

Difficulty: Hard

Paid? No

Companies: PhonePe

Problem Description

You are given an infinite grid and start at point (1, 1). In one step you may move from (x, y) to one of these points:

  • (x, y - x)
  • (x - y, y)
  • (2 * x, y)
  • (x, 2 * y)

Determine if you can reach the target point (targetX, targetY) from (1,1) using a finite sequence of these moves.

Key Insights

  • The subtraction moves (x, y - x) and (x - y, y) preserve the greatest common divisor (gcd) of the coordinates.
  • The doubling moves (2x, y) and (x, 2y) may multiply the gcd by 1 or 2.
  • Starting at (1,1) (where gcd = 1, which is 2^0) the gcd of any reachable point must be a power of 2.
  • Therefore, (targetX, targetY) is reachable if and only if gcd(targetX, targetY) is a power of 2.

Space and Time Complexity

Time Complexity: O(log(min(targetX, targetY))) due to the Euclidean algorithm for computing gcd.
Space Complexity: O(1)

Solution

This solution leverages the invariant that subtracting one coordinate from the other does not change their gcd, and doubling moves can only multiply the gcd by a factor of 2. Since the start point (1,1) has a gcd of 1 (2^0), the target point (targetX, targetY) must have a gcd that is a power of 2 to be reachable. We use the Euclidean algorithm to compute the gcd and then check if it is a power of 2 by ensuring it has exactly one set bit in its binary representation (i.e., n & (n-1) == 0).

Code Solutions

def isReachable(targetX: int, targetY: int) -> bool:
    # Helper function to compute gcd using the Euclidean algorithm
    def gcd(a: int, b: int) -> int:
        while b:
            a, b = b, a % b
        return a

    # Compute the gcd of targetX and targetY
    common_gcd = gcd(targetX, targetY)
    # Check if common_gcd is a power of two:
    # A number is a power of 2 if it has exactly one '1' in its binary representation.
    return common_gcd & (common_gcd - 1) == 0

# Example usage
print(isReachable(6, 9))  # Expected output: False
print(isReachable(4, 7))  # Expected output: True
← Back to All Questions