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)
1public class Solution {
2 public boolean reachingPoints(int sx, int sy, int tx, int ty) {
3 while (tx > sx && ty > sy && tx != ty) {
4 if (tx > ty) tx %= ty;
5 else ty %= tx;
6 }
7 if (tx < sx || ty < sy) return false;
8 if (tx == sx) return (ty - sy) % sx == 0;
9 return (tx - sx) % sy == 0;
10 }
11}In Java, the logic remains the same. The use of a while loop along with conditions checks ensures the reduction of values using reverse operation logic, making it optimal to check whether reaching (sx, sy) is possible.
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
1 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);
}
public bool ReachingPoints(int sx, int sy, int tx, int ty) {
return Reach(sx, sy, tx, ty);
}
}C# uses similar recursive calls to investigate forward potential moves assisting the solution pathway. Though a conceptual choice, practically it shows inefficiency due to redundant deep recursive logic when faced with large input ranges.