/*
 * You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly z litres using these two jugs.
 *
 * If z liters of water is measurable, you must have z liters of water contained within one or both buckets by the end.
 *
 * Operations allowed:
 *
 * Fill any of the jugs completely with water.
 * Empty any of the jugs.
 * Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.
 */
// TLE: 19 / 33 test cases passed.
public class Solution {
    public boolean canMeasureWater(int x, int y, int z) {
        // 1:05 - 1:33
        List<Integer> xcan = new ArrayList();
        List<Integer> ycan = new ArrayList();
        xcan.add(x);
        ycan.add(y);
        int pre_len_xcan = 0, pre_len_ycan = 0;
        while(xcan.size() > pre_len_xcan || ycan.size() > pre_len_ycan) {
            for(Integer xcani : xcan) {
                if(xcani < y) {
                    if(!ycan.contains(xcani)) ycan.add(xcani);
                }
            }
            for(Integer ycani : ycan) {
                if(ycani < x) {
                    if(!xcan.contains(ycani)) xcan.add(ycani);
                }
            }
            int xn = xcan.size(), yn = ycan.size();
            for(int i = 0; i < xcan.size(); i++) {
                int xcani = xcan.get(i);
                for(int j = 0; j < ycan.size(); j++) {
                    int ycani = ycan.get(j);
                    int curr = Math.abs(xcani - ycani);
                    if(curr < x) {
                        if(!xcan.contains(curr)) xcan.add(curr);
                    }
                    if(curr < y) {
                        if(!ycan.contains(curr)) ycan.add(curr);
                    }
                }
            }
            pre_len_xcan = xcan.size();
            pre_len_ycan = ycan.size();
        }
        int n = xcan.size();
        for(int i = 0; i < n; i++) {
            xcan.add(xcan.get(i) + y);
        }
        n = ycan.size();
        for(int i = 0; i < n; i++) {
            ycan.add(ycan.get(i) + x);
        }
        return xcan.contains(z) || ycan.contains(z);
    }
}

// v2: math - Bézout's identity
public class Solution {
    public boolean canMeasureWater(int x, int y, int z) {
        // 9:42 - 9:50
        if(z == 0) return true;
        // if(x == 0) return z == y;
        // if(y == 0) return z == x;
        if(z <= x + y && z % gcd(x, y) == 0) return true;
        return false;
    }
    private int gcd(int a, int b) {
        if(b == 0) return a;
        return gcd(b, a % b);
    }
}
