# 365. Water and Jug Problem 水壶问题

@TOC

## # 题目描述

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 "Die Hard" example)

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

Example 2:

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

## # 解题方法

### # 数学题

`z = m * x + n * y`

``````class Solution(object):
def canMeasureWater(self, x, y, z):
"""
:type x: int
:type y: int
:type z: int
:rtype: bool
"""
return z == 0 or (x + y >= z and z % self.gcd(x, y) == 0)

def gcd(self, x, y):
return x if y == 0 else self.gcd(y, x % y)
``````

## # 参考资料

http://www.cnblogs.com/grandyang/p/5628836.html

## # 日期

2018 年 10 月 31 日 —— 十月最后一天，万圣节