Last Updated: 29 Dec, 2020

Reach the destination

Easy

Asked in companies

Solve now

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)

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

Solve now

Approaches

01 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.

Solve now

02 Approach

The main idea of this approach is to iterate backward from the destination (dx, dy). We can determine which coordinate (x or y of destination point) was last changed, by selecting the larger of two. This will reduce the time complexity from exponential to linear since we are making just one recursive call for each valid pair of coordinates.

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 the 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
- reachDestination(sx, sy, dx - dy, dy), if dx > dy.
- Else reachDestination(sx, sy, dx, dy - dx).

Solve now