Check if possible to move from given coordinate to desired coordinate - GeeksforGeeks
Read full article from Check if possible to move from given coordinate to desired coordinate - GeeksforGeeks
Given two coordinates (x, y) and (a, b). Find if it is possible to reach (x,y) from (a,b).
Only possible moves from any coordinate (i, j) are
- (i-j, j)
- (i, i-j)
- (i+j, j)
- (i, i+j)
Given x, y, a, b can be negative.
If we take a closer look at the problem, we can notice that the moves are similar steps of Euclidean algorithm for finding GCD. So, it is only possible to reach coordinate (a, b) from (x, y) if GCD of x, y is equal to GCD of a, b. Otherwise, it is not possible.
Let GCD of (x, y) be gcd. From (x, y), we can reach (gcd, gcd) and from this point, we can reach to (a, b) if and only if GCD of ‘a’ and ‘b’ is also gcd.
int gcd(int i, int j){ if (i == j) return i; if (i > j) return gcd(i - j, j); return gcd(i, j - i);}// Returns true if it is possble to go to (a, b)// from (x, y)bool ispossible(int x, int y, int a, int b){ // Find absolute values of all as sign doesn't // matter. x = abs(x), y = abs(y), a = abs(a), b = abs(b); // If gcd is equal then it is possible to reach. // Else not possible. return (gcd(x, y) == gcd(a, b));}