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)
1#include <iostream>
2using namespace std;
3
4class Solution {
5public:
6 bool reachingPoints(int sx, int sy, int tx, int ty) {
7 while (tx > sx && ty > sy && tx != ty) {
8 if (tx > ty) tx %= ty;
9 else ty %= tx;
10 }
11 if (tx < sx || ty < sy) return false;
12 if (tx == sx) return (ty - sy) % sx == 0;
13 return (tx - sx) % sy == 0;
14 }
15};This C++ solution follows the same approach as the C solution. It iteratively applies reverse operations on (tx, ty) until one of them becomes equal to (sx, sy) or it's impossible (negative conditions). The use of the modulus operation ensures the reduction is done efficiently.
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
The Python recursive approach pursues feasibility by exploring both possible moves repeatedly until the base condition (goal reached or surpassed) is met. It clearly suffers from larger-than-efficient computation with high endpoint values due to the non-optimal nature of recursive exploration.