题目描述

有两个容量分别为 x升 和y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？
如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升水。
你允许：

• 装满任意一个水壶
• 清空任意一个水壶
• 从一个水壶向另外一个水壶倒水，直到装满或者倒空

示例

示例 1：

输入: x = 3, y = 5, z = 4
输出: True

示例2：

输入: x = 2, y = 6, z = 5
输出: False

解答方法

方法一：数学法

思路

如果gcd(x,y) = k ，那么肯定有整数（正的或负的）m与n，使得 mx + ny = k
如果z % k == 0, 那么mx + ny = k那么必定存在一个常数g使得g(mx + ny) == k * g == z
所以题目就转换为寻找x，y的最大公约数。

代码

class Solution:
    def canMeasureWater(self, x: int, y: int, z: int) -> bool:
        if x+y<z:
            return False
        if z == 0 or x+y ==z:
            return True
        return z%math.gcd(x,y) == 0
# def gcd(a,b):
#     if b==0:
#         return a
#     else:
#         return gcd(b, a%b)

时间复杂度

O(log(min(x,y)))，取决于计算最大公约数所使用的辗转相除法。

空间复杂度

O(1)O(1)，只需要常数个变量。