# Reaching Points

Posted: 28 Feb, 2021

Difficulty: Moderate

#### 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:**

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

Approach 2

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,

SIMILAR PROBLEMS

# Ninja Class

Posted: 26 Oct, 2021

Difficulty: Moderate

# Matrix multiplication

Posted: 5 Nov, 2021

Difficulty: Easy

# Subsequence Product

Posted: 25 Nov, 2021

Difficulty: Hard

# Kth Smallest Natural Number After Removing Some Numbers

Posted: 25 Nov, 2021

Difficulty: Moderate

# Ninja And The LCM

Posted: 12 Apr, 2022

Difficulty: Easy