365. Water and Jug Problem

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: **

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

Example 2:

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

这道题实际上是道数学智力题，求解的关键就是判断z能否整除x与y的最大公约数。当然，这道题有些隐藏约束，就是z<=x+y以及z可以为0，当然多过几遍测试用例基本上就能察觉了。上代码：

/**
 * @param {number} x
 * @param {number} y
 * @param {number} z
 * @return {boolean}
 */
var canMeasureWater = function (x, y, z) {
    const findDivisor = function (a, b) {
        while (b) {
            let c = a % b;
            a = b;
            b = c;
        }
        return a;
    };
    const divisor = findDivisor(x, y);
    if (z > x + y) {
        return false;
    }
    else if (z === x || z === y || z === 0) {
        return true;
    }
    return (z % divisor === 0);
};

需要一些优化的地方可能就是找最大公约数了，这里我选用了辗转相除的方法。当然也有辗转相减和暴力循环的方式。具体算法可以自行百度一下。