Taro Logo

Check if Point Is Reachable

#6 Most AskedHard
6 views
Topics:
Graphs

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

Constraints:

  • 1 <= targetX, targetY <= 109

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. Does every path start at the point whose coordinates are both one?
  2. Does doubling change only one coordinate, leaving the other coordinate the same?
  3. Is subtraction allowed only when the result stays positive?
  4. Should the answer be a boolean, without returning the path itself?
  5. Are those two kinds of moves the only moves allowed?

Brute Force Solution

Approach

The search works backward from the target toward the start. An even coordinate can be halved, and the larger coordinate can be reduced by the smaller one. A point is reachable when the start appears, and each point is explored only once.

Here's how the algorithm would work step-by-step:

  1. Begin with the target as the only point waiting to be explored.
  2. If the point being explored is the start, return true.
  3. If the first coordinate is even, enqueue the point with that coordinate halved.
  4. If the second coordinate is even, enqueue the point with that coordinate halved.
  5. If one coordinate is larger than the other, enqueue the point formed by subtracting the smaller from the larger.
  6. Skip any point that has already been explored, and return false when no points remain.

Code Implementation

class Solution:
    def isReachable(self, target_x: int, target_y: int) -> bool:
        points_to_visit = set([(target_x, target_y)])
        visited_points = set()

        while points_to_visit:
            current_x, current_y = points_to_visit.pop()

            if current_x == 1 and current_y == 1:
                return True
            
            if (current_x, current_y) in visited_points:
                continue
            
            visited_points.add((current_x, current_y))

            # We explore backwards, so if we're at an even number, we could have come from half of it.
            if current_x % 2 == 0:
                previous_point = (current_x // 2, current_y)
                if previous_point not in visited_points:
                    points_to_visit.add(previous_point)

            if current_y % 2 == 0:
                previous_point = (current_x, current_y // 2)
                if previous_point not in visited_points:
                    points_to_visit.add(previous_point)

            # The reverse move for (x+y) is (x, y-x) or (x-y, y).
            if current_y > current_x:
                previous_point = (current_x, current_y - current_x)
                if previous_point not in visited_points:
                    points_to_visit.add(previous_point)

            if current_x > current_y:
                previous_point = (current_x - current_y, current_y)
                if previous_point not in visited_points:
                    points_to_visit.add(previous_point)

        # If the loop finishes without finding (1, 1), it's unreachable.
        return False

Big(O) Analysis

Time Complexity
O(x * y) – Let x and y be the two target coordinates. Every point placed in the frontier has coordinates between zero and those targets, so there are at most x times y distinct points. Each point is expanded once. From one point there are only a few reverse moves, and each move is constant work. The total time is O(x * y).
Space Complexity
O(x * y) – Let x and y be the two target coordinates. The frontier and the set of visited points can each contain every reachable lattice point inside the rectangle from the origin to the target. That rectangle has O(x * y) points. No other structure is stored. The extra space is O(x * y).

Optimal Solution

Approach

A target is reachable exactly when the greatest common divisor of its two coordinates is a power of two, including two to the power zero, which is one. The divisor is computed by repeated remainder, the same way Euclid's algorithm works. A positive number is a power of two when it shares no bits with the number one smaller than itself.

Here's how the algorithm would work step-by-step:

  1. If either coordinate is zero, its divisor is the other coordinate.
  2. Otherwise replace the larger coordinate by the remainder of dividing it by the smaller one.
  3. Repeat until one coordinate becomes zero, and take the other coordinate as the divisor.
  4. Reject a non-positive divisor.
  5. Accept the divisor when it shares no bits with one less than itself, which is true for one and for every higher power of two.

Code Implementation

class Solution:
    def isReachable(self, target_x: int, target_y: int) -> bool:

        def greatest_common_divisor(number_one, number_two):
            while number_two:
                number_one, number_two = number_two, number_one % number_two
            return number_one

        # The GCD of reachable coordinates is preserved through reverse operations (subtraction).
        # All reachable points must trace back to a state where GCD is related to the initial (1,1) state.
        common_divisor = greatest_common_divisor(target_x, target_y)

        # Any number that is a power of 2 can be repeatedly divided by 2 until it becomes 1.
        # This means we can transform (2^k, 2^k) down to (1, 1), making the target reachable.
        is_power_of_two = (common_divisor > 0) and (common_divisor & (common_divisor - 1) == 0)

        return is_power_of_two

Big(O) Analysis

Time Complexity
O(log(min(x, y))) – Let x and y be the two coordinates. Each remainder step replaces the larger coordinate with a strictly smaller non-negative value. The number of steps is proportional to the number of digits of the smaller coordinate, which is O(log(min(x, y))). The power-of-two test is a constant number of bit operations. The total time is O(log(min(x, y))).
Space Complexity
O(1) – Only the two coordinates and their remainder are stored while the divisor is computed. The power-of-two test uses those same values. No list of points is kept. The extra space is O(1).

Edge Cases

The target is already the starting point
How to Handle:
The search recognizes it immediately, and the divisor of the two coordinates is one, which is a power of two.
The target is four and seven
How to Handle:
Both versions accept it because a sequence of the allowed moves reaches that point.
The target is six and nine
How to Handle:
Both versions reject it because the greatest common divisor is three, which is not a power of two.
One coordinate is one and the other is a power of two
How to Handle:
The point is reachable, since the divisor is one.
Both coordinates are odd and greater than one
How to Handle:
The point is reachable only when their greatest common divisor is one.
0/98 completed