Reaching Points

Moderate
0/80
Average time to solve is 30m
21 upvotes
Asked in companies
Goldman SachsUberSalesforce

Problem statement

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

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1
2
1 1 5 8
3 5 7 9
Sample Output 1:
true  
false

Explanation For Sample Input 1:

For the first test case, the sequence of moves
(1,1)->(2,1)
(2,1)->(2,3)
(2,3)->(5,3)
(5,3)->(5,8)
Hence the answer for this case is true.

For the second test case, there is not a possible sequence to reach the final points.
Sample Input 2
2
1 1 1 1000
1 1 1000 1
Sample Output 2
true
true
Hint

Think of BFS to solve this problem.

Approaches (2)
Breadth First Search

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.
Time Complexity

O(N) where N is max(targetX-startX,targetY-startY) 

 

In worse case to reach targetX and targetY will take max(targetX - startX, targetY - startY) steps.

Space Complexity

O(N) where N is max(targetX - startX, targetY - startY)

 

In worse case queue will store  max(targetX - startX, targetY - startY) vertices.

Code Solution
(100% EXP penalty)
Reaching Points
Full screen
Console