# Question

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


# Solution

This is a pure Math problem. The basic idea is to use the property of Bézout’s identity and check if z is a multiple of GCD(x, y) (greatest common divider).

Bézout’s identity — Let a and b be integers with greatest common divisor d. Then, there exist integers x and y such that ax + by = d. More generally, the integers of the form ax + by are exactly the multiples of d.

Assume $$f(a, b) = ax + by$$ to be total amount of water in both jugs, then the three operations become:

1. Increment a or b by 1 (fill jug with water);
2. Decrement a or b by 1 (empty any of the jugs);
3. Pour water from one jug to the other does not change the value of f.

Thus, if z is a multiple of GCD(a, b), then there exists a, b such that ax + by == z.

class Solution:
def canMeasureWater(self, x, y, z):
"""
:type x: int
:type y: int
:type z: int
:rtype: bool
"""
if z == 0:
return True
if x + y < z:
return False

return z % self.gcd(x, y) == 0

def gcd(self, a, b):
if b > a:
a, b = b, a
while b != 0:
tmp = b
b = a % b
a = tmp
return a