Leetcode: Reaching Points

 

This question is asked very commonly at Goldman Sach's. 

A move consists of point (x,y) and transforms it to either (x, x + y) or (x + y, y). Given a starting point (sx, sy) and a target point (tx, ty) return True if and only if a sequence of moves exist to transform the point (sx,  sy) to (tx, ty) otherwise return False. Here's an example: 

Examples:

Input: sx = 1, sy = 1, tx = 3, ty = 5

Output: True

Explanation:

One series of moves that transforms the starting point to the target is:

(1, 1) -> (1, 2)

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

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

Input: sx = 1, sy = 1, tx = 2, ty = 2

Output: False

Input: sx = 1, sy = 1, tx = 1, ty = 1

Output: True

And here is the range:

sx, sy, tx, ty will all be integers in the range [1, 10^9].

If I observe things carefully, there are 2 actions that I can take which are (x, x + y) and (x + y, y). This means we can have 2 choices at (x, y) which forms a binary tree. You can try top-down and run from the top to the bottom of a binary tree, and then find the leaf node that satisfies the condition. 

There is also a boundary condition which is based on whether sx > tx or sy > ty i the binary tree, and we return whether we reached the points on the left side of the tree or the right side of the tree. Such is the top-down optimization: 

public static boolean reachingPoints(int sx, int sy, int tx, int ty) {

    //see if we reach the equivalent point

    if(sx == tx && sy == ty) {

        return true;

    }

    //if we have a point that is greater, then we have already long passed

    if(sx > tx || sy > ty) {

        return false; 

    }

    //return if we have reached the case if we added sx to the reverse, or vice versa. 

    return (reachingPoints(sx + sy, sy, tx, ty) || reachingPoints(sx, sx + sy, tx, ty));

}

Now there is a bottom-up approach, and we can try to go up one we have a condition like sx <= tx or sy <= ty. There is only 1 way to reach the root from the binary tree. Let sx = 1, sy = 1, tx = 3, and ty = 5.

The first step is if 2 target points are bigger than the  2 starting points, we reduce the taget points, and we want to check if we reduced the target points. The next parent operations will be to subtract ty from px until the time that tx %= ty which we can replace with while tx > ty: tx -= ty. Else if tx > ty and ty <= sy, then we know that only tx changes at this time, and it can only be changed by subtracting ty. So (tx - sx) % ty == 0 is a necessary condition. 

public boolean reachingPoints(int sx, int sy, int tx, int ty){

    while(sx < tx && sy < ty)

        if (tx < ty) ty %= tx;

        else tx %= ty;

        return sx == tx && sy <= ty && (ty - sy) % sx == 0 || sy == ty && sx <= tx && (tx - sx) % sy == 0;

}

And the final code form is as follows: 

class Solution {

    public boolean reachingPoints(int sx, int sy, int tx, int ty) {

        while(tx >= sx && ty >= sy) {

            //anything else would get one of the values to 0, which is not what we want 

            if(tx == ty) break;

            //if tx is greater keep reducing the value and then reduce the ty value.

            if(tx > ty) {

                if(ty > sy) tx % ty;

                else return (tx - sx) % ty == 0;

            //if ty is greater then reduce this value else we can only reduce the tx value now, so do that.

            } else {

                if(tx > sx) ty %= tx;

                else return (ty - sy) % tx == 0;

            }

        }

        //check if these 2 values are equal to each other.

        return (tx == sx && ty == sy);

    }

}

So mods can continuously subtract values and check to see if something is a multiple.