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.
- 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
Input: x = 2, y = 6, z = 5 Output: False
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:
- Increment a or b by 1 (fill jug with water);
- Decrement a or b by 1 (empty any of the jugs);
- 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