Given four integers sx, sy, tx, and ty, return true if it is possible to convert the point (sx, sy) to the point (tx, ty) through some operations, or false otherwise.
The allowed operation on some point (x, y) is to convert it to either (x, x + y) or (x + y, y).
Example 1:
Input: sx = 1, sy = 1, tx = 3, ty = 5 Output: true Explanation: One series of moves that transforms the starting point to the target is: (1, 1) -> (1, 2) (1, 2) -> (3, 2) (3, 2) -> (3, 5)
Example 2:
Input: sx = 1, sy = 1, tx = 2, ty = 2 Output: false
Example 3:
Input: sx = 1, sy = 1, tx = 1, ty = 1 Output: true
Constraints:
1 <= sx, sy, tx, ty <= 109The goal could be efficiently approached by reversing the operations. Instead of trying to reach (tx, ty) from (sx, sy), we attempt to determine whether (sx, sy) can be reached from (tx, ty) using reverse operations. This is achieved by repeatedly applying the inverse operations: (x, x+y) can be reverted to (x, y), and (x+y, y) can be reverted to (x, y). The main idea is to use modulus operations when x != y.
This solution uses a loop to apply the reverse operations until tx or ty is reduced to sx or sy. It checks if further reduction is possible using modulus operations, ensuring the feasibility of reaching (sx, sy) based on the remainder. The logic ensures that one either complements the other by reducing one coordinate using the other. This approach is efficient due to its use of modulus operation, providing a quick reduction of the problem space.
C++
Java
Python
C#
JavaScript
Time Complexity: O(log(max(tx, ty)))
Space Complexity: O(1)
Another strategy involves recursive backtracking, where the function makes recursive calls to simulate both directions (x + y, y) and (x, x + y) to reach the target point (tx, ty) from the start point (sx, sy). Although less efficient compared to the reverse operation method due to its depth, it's an introductory way to explore the possibilities.
The backtracking approach uses recursion to simulate both possible moves at each step, verifying if any combination of moves can transition the start point into the target point. However, this implementation will face efficiency issues with larger inputs due to recursive depth and repeated evaluations.
C++
Java
Python
C#
JavaScript
Time Complexity: Exponential in the worst case
Space Complexity: Recursive stack size
| Approach | Complexity |
|---|---|
| Reverse Operation Approach | Time Complexity: O(log(max(tx, ty))) |
| Recursive Backtracking Approach | Time Complexity: Exponential in the worst case |
How I ACTUALLY got good at Leetcode • NeetCode • 151,421 views views
Watch 9 more video solutions →Practice Reaching Points with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor