365. Water and Jug Problem - cocoder39/coco39_LC GitHub Wiki

365. Water and Jug Problem

The problem actually is finding out if there exists a solution to z = a * x + b * y where a, b are integers. One solution is z = -1 * x + 2 * y, which is obtained by filling y twice and emptying x once. The problem can be solved through finding out if z is multiple of the gcd(x, y). Say x = 4, y = 6, z = 8, then z = a * x + b * y since z is multiple of gcd(x, y) = 2. corner case are z == 0, a == 0, b == 0 and z > x + y

gcd(a, 0) = a;
gcd(a, b) = gcd(b, a % b);

get greatest common divisor through Euclid's algorithm, which can be solved in polynomial time.

class Solution {
public:
    bool canMeasureWater(int x, int y, int z) {
        if (x + y < z) {
            return false;
        }
        return z == 0 || z % GCD(x, y) == 0;
    }
private:
    int GCD(int a, int b) {
        while (b != 0) {
            int tmp = b;
            b = a % b;
            a = tmp;
        }
        return a;
    }
};