Last Updated: 28 Feb, 2021

Reaching Points

Moderate

Asked in companies

Solve now

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

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

Solve now

Approaches

01 Approach

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:

Start the bfs traversal from (startX,startY) and enqueue this coordinate in the queue.
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.
Return false at the end since source vertex cannot be transformed into target vertex.

Solve now

02 Approach

The key idea is instead of starting from the source vertex start traversal in opposite direction. From source vertex 2 vertex is reachable (x,x+y) and (x+y,y) but from target vertex, only 1 vertex needed to be traversed.For Ex-(targetX=5,targetY=7.The opposite traversal can be (5,2) and (-2,7) but both coordinates must be greater than 0. Hence only (5,2) is valid.)

Here is the algorithm:

Run a loop until targetX>sourceX and targetY>sourceY
if(targetX>targetY) then do targetX%=targetY.(For Ex-targetX=x’+k*targetY. Instead of subtracting targetY k times from targetX it could be simply done targetX%=targetY.It will take just one step instead of k to become less than targetY.
Similarly if targetY>targetX do targetY%=targetX.
Now check if targetX==sourceX and targetY>=sourceY and (targetY-sourceY)%targetX==0 simply returns true.The reason we are doing this if targetX==sourceX so targetX should not be reduced further.Need to reduce only from targetY.If targetY-sourceY is a multiple of targetX then it means targetY can be converted into sourceY.Hence return true.
Similarly check targetY==sourceY and targetX>=sourceX and (targetX-sourceX)%targetY==0 then return true.
If Both the above conditions are not true then return false,

Solve now