Optimal way to determine If it is possible to arrive at pair (c,d) when starting from (a,b)

Question

Every pair (a,b) can be transformed to either (a+b, b) or (a, a+b).

Given a function bool isPossible(int a, int b, int c, int d) , Implement the logic that returns true or false depending upon whether target pair of (c,d) can be reached via (a,b)

// (a,b) -> (a, a+b)
// (a,b) -> (a+b,b)
// 2,3 -> 2,5 | 5,3 -> 7,5 | 2, 7 | 5, 8 | 8, 3 -> 12, 5 | 7, 12 | 9, 7 | 2, 9 |5, 13|13,8 | 11, 3 | 8, 11
// a,b -> a,a+b | a+b, b -> a, 2a+b | 2a +b , a+b | a+b, a+2b | a+2b, b -> a, 3a + b | 3a + b , 2a +b |

Update: Adding my Solution here. Would be interesting to look for other elegant solutions to this.

bool isPossible(int a,int b,int c,int d) {

    while(c>=a && d>=b) {
        if(a == c && b==d ) {
            return true;
        }
        int temp = c;
        c= c>d?c-d:c;
        d= d>=temp?d-temp:d;
    }
    return false;
}

Update: This solution seems to work only for the positive values of a and b.

Answer 1

Your solution is based on the idea that it is better to walk backwards, i.e. from (c,d) to (a,b). This is because when you start from (a,b) and go forward, you have two possibilities for the next pair, while when you start from (c,d) and go backward, you apparently have only one possibility — you need to substract the smallest value from the largest one.

This is indeed true for the case when both a and b are positive. In this case, a+b>a and a+b>b, and thus given a (c,d) pair it is easy to determine which step in the chain of transformations was the last (it depends in whether c>d or d>c). However, this reasoning breaks if a or b can be negative, as in this case you do not know whether you should subtract c from d or vice versa. This is a fundamental problem in your approach, and I do not see simple ways to overcome it.

If we consider only the case of positive a and b, then we can modify your solution to a more effective one.

Consider the case when c is much bigger than d. In this case, you will be subtracting d from c for many times, up to a point when new c becomes smaller than d. What you will arrive at the end to? Obviously to (c%d, d). So you can do it in one step, coming to a code that is very similar to Euclidean algorithm for the greatest common divisor.

However, with such jumping from subtractions to modulo division, you may have actually skipped the needed pair (i.e. (a,b)). However, this is simple to fix because one of the numbers does not change, so we can easily determine such a situation.

The code will be something like the following (not tested)

while (c > 0 && d > 0) {  // similar to how Eucledian algorithm is written
    if (c > d) {
        int new_c = c % d;
        if (b == d) {  // we should have seen (a,b) here
            return (a % d == new_c && a >= new_c && a <= c);
        }
        c = new_c;
    } else {
        //  a symmetrical case follows
        ...
    }
} 

This code has time complexity O(log(c + d)), while your code with subtractions works in O(c+d).

---

As for the case when a and/or b can be negative, this seems to be a much more difficult problem.

Answer 2

I have no (mathematical) proof yet, but this function:

static boolean myPossible(int a, int b, int c, int d) {
  // parenthesis not needed, but for better human readability...
  return (c % a == b && d % b == a) || (c % b == a && d % a == b);
}

...returns (always) the same results as yours!

"numerical/brute force test":

public class Test {

    private static final Random RAND = new Random();

    public static void main(String[] args) {

        for (int i = 0; i < 1000000; i++) {
            // temporarily set to 0..1 (corner case)
            int a = RAND.nextInt(1);
            // temporarily set to 0..1 (corner case)
            int b = RAND.nextInt(1);
            int c = RAND.nextInt(10000);
            int d = RAND.nextInt(10000);
            assert (isPossible(a, b, c, d) == myPossible(a, b, c, d));
        }
    }

    static boolean isPossible(int a, int b, int c, int d) {
        while (c >= a && d >= b) {
            c = c > d ? c - d : c;
            d = d >= c ? d - c : d;
            if (a == c && b == d) {
                return true;
            }
        }
        return false;
    }

    static boolean myPossible(int a, int b, int c, int d) {
        return c % a == b && d % b == a || c % b == a && d % a == b;
    }
}