ReachingPoints.java

package math;

/**
 * Created by gouthamvidyapradhan on 14/07/2018.
 * A move consists of taking a point (x, y) and transforming 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 exists
 to transform the point (sx, sy) to (tx, ty). Otherwise, return False.

 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

 Note:

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

 Solution: Start from the target, reduce the target value to start value.
 If at any stage the target value goes below start value then there exist no solution hence return false.
 */
public class ReachingPoints {

    class Pair{
        int x, y;
        Pair(int x, int y){
            this.x = x;
            this.y = y;
        }
    }

    /**
     * Main method
     * @param args
     * @throws Exception
     */
    public static void main(String[] args) throws Exception{
        System.out.println(new ReachingPoints().reachingPoints(1, 1, 153, 10));
    }

    public boolean reachingPoints(int sx, int sy, int tx, int ty) {
        Pair target = new Pair(tx, ty);
        Pair start = new Pair(sx, sy);
        while(true){
            if(start.x == target.x && start.y == target.y){
                return true;
            } else if(start.x > target.x || start.y > target.y || target.x == target.y){
                return false;
            } else if(start.x == target.x){
                int t = target.y - start.y;
                return (t % target.x) == 0;
            } else if(start.y == target.y){
                int t = target.x - start.x;
                return (t % target.y) == 0;
            } else{
                if(target.x > target.y){
                    int[] R = reduce(target.x, target.y);
                    target.x = R[0];
                    target.y = R[1];
                } else {
                    int[] R = reduce(target.y, target.x);
                    target.x = R[1];
                    target.y = R[0];
                }
            }
        }
    }

    private int[] reduce(int x, int y){
        int t = x - y;
        int q = t / y;
        x -= (y * q);
        if((t % y) != 0){
            x -= y;
        }
        return new int[]{x, y};
    }
}