Reaching Points — Asked in Goldman Sachs and Uber Interview

Problem Statement :

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

The first and the only line of each test case contains 4 integers startX, startY, endX and endY

Sample Input:

1 1 5 8

Sample Output:

true

Explanation of Sample Test Case:

Here are the sequence of moves for given test case:-

(1,1)->(2,1)
(2,1)->(2,3)
(2,3)->(5,3)
(5,3)->(5,8)

Hence the answer for this case is true.

Approach :

The key idea is instead of starting from source vertex start traversal in opposite direction. From source vertex 2 vertex are 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.)

The algorithm will be -

1. Run a loop until targetX>sourceX and targetY>sourceY
2. 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.
3. Similarly if targetY>targetX do targetY%=targetX.
4. 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.
5. Similarly check targetY==sourceY and targetX>=sourceX and (targetX-sourceX)%targetY==0 then return true.
6. If Both the above conditions are not true then return false.

Time Complexity : O(log(min(endX,endY))
Space Complexity : O(1)

Code :

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.