Reaching Points

Posted: 28 Feb, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

Given a starting point (startX, startY) and target point(endX, endY) . Return true if there is a sequence of moves to transform the starting point into the ending point. In one move you can transform (x, y) to either (x + y, y) or (x, x + y).

Input Format
The first line of input contains an integer ‘T’ denoting the number of test cases.

The next ‘T’ lines represent the test cases.

The first and the only line of each test case contains 4 integers startX,startY,endX, and endY.
Output Format
For each test case, print true if there is a sequence of moves to transform the starting point into the ending point, otherwise print false.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints
1 <= ’T’ <= 50
1 <= ’startX’, ’startY’, ’targetX’, ’targetY’ <= 10^9
‘startX’, ’startY’ denotes starting coordinates.
‘endX’, ’endY’ denotes target  coordinates. 

Time Limit: 1 sec
Approach 1

The key id is to do bfs traversal from (startX, startY) to (targetX, targetY).If it is possible to reach targetX, targetY return true.

 

Here is the Algorithm:

  1. Start the bfs traversal from (startX,startY) and enqueue this coordinate in the queue.
  2. Iterate until the queue is not empty and perform the following operations:
    • Dequeue the vertex present at the front of the queue.
    • If the vertex is equal to targetX and targetY return true
    • If either x coordinate or y coordinate of current vertex  is greater than targetX or targetY then the current vertex cannot be transform into target vertex
    • Else enqueue (currX, currX + currY) and (currX + currY, currY) into queue.
  3. Return false at the end since source vertex cannot be transformed into target vertex.
Try Problem