Problem Description
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.
Key Insights
- Starting from (1, 1), we can apply moves that either reduce one coordinate or double one coordinate.
- The operations allow us to manipulate the coordinates in a way that can be reversed; hence we can also think about reaching (targetX, targetY) from (1, 1) by considering the reverse operations.
- The key is to reduce either targetX or targetY to 1 through a series of allowed operations while checking for validity.
Space and Time Complexity
Time Complexity: O(log(max(targetX, targetY)))
Space Complexity: O(1)
Solution
To determine if the point (targetX, targetY) is reachable from (1, 1), we can use a reverse approach. Starting from (targetX, targetY), we repeatedly apply the reverse operations until we either reach (1, 1) or determine that it's impossible. The reverse operations are:
- If targetX > targetY, we can replace targetX with targetX - targetY.
- If targetY > targetX, we can replace targetY with targetY - targetX.
- If one of the coordinates is even, we can also divide that coordinate by 2. This process continues until either of the coordinates becomes 1 or we can no longer reduce them meaningfully.