Reach the destination

Easy
0/40
Average time to solve is 15m
profile
Contributed by
73 upvotes
Asked in companies
MakeMyTripAmerican ExpressSamsung

Problem statement

Given a source point (sx, sy) and a destination point (dx, dy), the task is to check if it is possible to reach the destination point using the following valid moves:

(a, b) -> (a + b, b)
(a, b) -> (a, a + b)

Your task is to find if it is possible to reach the destination point using only the desired moves or not.

For example: 
For the coordinates, source point = (1, 1) and destination point = (3, 5)
The output will be true as the destination point can be reached using the following sequence of moves:
(1, 1) -> (1, 2) -> (3, 2) -> (3, 5)
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer ‘T’ representing the number of test cases. Then the test cases follow.

The only line of each test case contains four space-separated integers sx, sy, dx, and dy where sx, sy represents the coordinates of the source point and dx, dy represents the coordinates of the destination point.
Output Format: 
For each test case, return the boolean true if the destination point can be reached from the source point using only the desired moves, else return false.

The output for each test case is to be printed on a separate line.
Note: 
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 100
1 <= x, y <= 3000

Where ‘T’ is the number of test cases and ‘x’, ‘y’ are the coordinates of the given points.

Time Limit: 1sec
Sample Input 1:
2
1 1 3 5
1 1 1 4
Sample Output 1:
True
True
Explanation For Sample Input 1:
For the first test case
The output will be true as destination point can be reached using the following sequence of moves:
(1, 1) -> (1, 2) -> (3, 2) -> (3, 5)

For the second test case
The output will be true as destination point can be reached using the following sequence of moves:
(1, 1) -> (1, 2) -> (1, 3) -> (1, 4)
Sample Input 2:
2
1 1 2 2
1 1 1 1
Sample Output 2:
False
True
Hint

Consider all the possible paths from the source cell to the destination cell with the help of recursion.

Approaches (2)
Brute force approach

The naive approach to solve this problem is to consider each and every possible move until we reach the destination.

 

This can be done using recursion. Below is the algorithm:

 

  • Check for the bases:
    • If the source and destination coordinates are the same, return true.
    • Return false, if the x (or y) coordinate of source point is greater than the x (or y) coordinate of the destination point. As there is no path to reach the destination.
  • Recursive call to the function for each valid move
    • Check if the destination can be reached by replacing x coordinate with both the coordinates of the source point.
    • Check if the destination can be reached by replacing y coordinate with both the coordinates of the source point.
    • Return true, if either of the above two calls return true.
Time Complexity

O(2 ^ max(x, y)), where (x, y) is the coordinates of the destination point.

 

Since, for every valid pair of coordinates, each recursive call will end up in two recursive calls. Thus, the final time complexity will be exponential, i.e. O(2 ^ max(x, y)).

Space Complexity

O(max(x, y)), where (x, y) is the coordinates of the destination point.

 

We are using O(H) extra space for the call stack where ‘H’ is the height of the recursion tree, and it could be max(x, y) in the worst case.

Code Solution
(100% EXP penalty)
Reach the destination
Full screen
Console