Sponsored
Sponsored
The 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.
Time Complexity: O(log(max(tx, ty)))
Space Complexity: O(1)
1class Solution:
2 def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:
3 while tx > sx and ty > sy and tx != ty:
4 if tx > ty:
5 tx %= ty
6 else:
7 ty %= tx
8 if tx < sx or ty < sy:
9 return False
10 return (ty - sy) % sx == 0 if tx == sx else (tx - sx) % sy == 0Python makes this logic concise with its simple syntax. The logic is identical, where reverse operations are applied until reduction is achieved or deemed impossible. Modulus operations work well in reducing the situation to its origin.
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.
Time Complexity: Exponential in the worst case
Space Complexity: Recursive stack size
1using namespace std;
class Solution {
public:
bool reach(int sx, int sy, int tx, int ty) {
if (sx > tx || sy > ty) return false;
if (sx == tx && sy == ty) return true;
return reach(sx + sy, sy, tx, ty) || reach(sx, sy + sx, tx, ty);
}
bool reachingPoints(int sx, int sy, int tx, int ty) {
return reach(sx, sy, tx, ty);
}
};This C++ code implements recursion to query both directions from the start point, assessing if the end point is achievable. The depth and repetitiveness of calls make it less optimal than the iterative modulus-based approach.