Check Possibility of Reaching Points

Given four integers X1, Y1, X2, and Y2, the task is to check if it is possible to convert the point (X1, Y1) to the point (X2, Y2) through some operations. The allowed operations on some point (X, Y) are to convert it to either (X, X+ Y) or (X + Y, Y).

Examples:

Input: X1 = 1, Y1 = 1, X2 = 3, Y2 = 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)
Input: X1 = 1, Y1 = 1, X2 = 2, Y2 = 2
Output: false
Explanation: It is not possible to convert (1, 1) to (2, 2) using the allowed operations.

Approach:

To determine whether it is possible to convert (X1, Y1) to (X2, Y2) using the allowed operations, we can reverse the problem. Instead of trying to build up from (X1, Y1) to (X2, Y2), we can work backwards from (X2, Y2) to (X1, Y1) using the inverse operations:

From (X, Y), if X >= Y, we can go back to (X – Y, Y).
If Y >= X, we can go back to (X, Y – X).
This reversal approach helps us efficiently check if we can reduce (X2, Y2) back to (X1, Y1).

Steps-by-step approach:

Start from the point (X2, Y2).
While (X2 > X1 && Y2 > Y1):
- If X2 > Y2, set X2 = X2 % Y2.
- Else, set Y2 = Y2 % X2.
After the loop, check if we can reach (X1, Y1) directly:
- If X1 == X2 and Y1 <= Y2 and (Y2 – Y1) % X1 == 0, return true.
- If Y1 == Y2 and X1 <= X2 and (X2 – X1) % Y1 == 0, return true.
Otherwise, return false.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>
using namespace std;

#include <iostream>

bool reachingPoints(int X1, int Y1, int X2, int Y2)
{
    // Step 2: Work backwards from (X2, Y2) to (X1, Y1)
    while (X2 > X1 && Y2 > Y1) {
        if (X2 > Y2) {
            X2 %= Y2; // Reduce X2 using modulo operation
        }
        else {
            Y2 %= X2; // Reduce Y2 using modulo operation
        }
    }

    // Step 3: Check if we can reach (X1, Y1) directly from
    // (X2, Y2)
    if (X1 == X2 && Y1 <= Y2 && (Y2 - Y1) % X1 == 0) {
        return true;
    }
    if (Y1 == Y2 && X1 <= X2 && (X2 - X1) % Y1 == 0) {
        return true;
    }

    // Step 4: If we cannot reach (X1, Y1), return false
    return false;
}

int main()
{
    // Example 1
    int X1 = 1, Y1 = 1, X2 = 3, Y2 = 5;
    cout << (reachingPoints(X1, Y1, X2, Y2) ? "true"
                                            : "false")
         << endl;

    return 0;
}

Java

import java.util.*;

public class ReachingPoints {

    public static boolean reachingPoints(int X1, int Y1, int X2, int Y2) {
        // Step 2: Work backwards from (X2, Y2) to (X1, Y1)
        while (X2 > X1 && Y2 > Y1) {
            if (X2 > Y2) {
                X2 %= Y2; // Reduce X2 using modulo operation
            } else {
                Y2 %= X2; // Reduce Y2 using modulo operation
            }
        }

        // Step 3: Check if we can reach (X1, Y1) directly from (X2, Y2)
        if (X1 == X2 && Y1 <= Y2 && (Y2 - Y1) % X1 == 0) {
            return true;
        }
        if (Y1 == Y2 && X1 <= X2 && (X2 - X1) % Y1 == 0) {
            return true;
        }

        // Step 4: If we cannot reach (X1, Y1), return false
        return false;
    }

    public static void main(String[] args) {
        // Example 1
        int X1 = 1, Y1 = 1, X2 = 3, Y2 = 5;
        System.out.println(reachingPoints(X1, Y1, X2, Y2) ? "true" : "false");
    }
}
// This code is contributed by Ayush Mishra

Output

true

Time Complexity: The while loop iterates as long as X2 > X1 and Y2 > Y1. In each iteration, the larger of X2 or Y2 is reduced by taking the modulo with the smaller one, which can be considered as logarithmic reduction in the worst case. Hence, the time complexity is approximately O(log max(X2,Y2)).

Auxiliary Space: O(1) as we are using a constant amount of extra space regardless of the input size.

Contact Us