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.

 

Example 1: (From the famous )

Input: x = 3, y = 5, z = 4Output: True

 

Example 2:

Input: x = 2, y = 6, z = 5Output: False

 

Credits:

Special thanks to  for adding this problem and creating all test cases.

 

/**

* Math problem

* 能测的体积是两个瓶子最大公约数的倍数

* 比较麻烦的是0 的情况！！

*/

/** * Math problem * 能测的体积是两个瓶子最大公约数的倍数 *  比较麻烦的是0 的情况！！ * 可用数论的知识 Bézout's identity 求最大公约数*/public class Solution {    public boolean canMeasureWater(int x, int y, int z) {        if(x+y < z) return false;        if(x == 0 && y == 0 && z == 0) return true;        if(x == 0 || y == 0 && z != 0) return false;        return z % gcd1(x,y) == 0;    }        // Bézout's identity    //let a and b be nonzero integers and let d be their greatest common divisor. Then there exist integers x and y such that ax+by=d    public int gcd1(int x, int y){          while(y != 0){            int temp = y;            y = x % y;            x = temp;        }        return x;    }        public int gcd2(int x, int y){        int res = 1;        int end = Math.min(x, y);        if(end == 1) return 1;        for(int i = 2; i <= end; i++){            if(x % i == 0 && y % i == 0)                res = i;        }        return res;    }}