365.Water and Jug Problem

Tags: [math], [gcd]

Link: https://leetcode.com/problems/water-and-jug-problem/#/description

You are given two jugs with capacitiesxandylitres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactlyzlitres using these two jugs.

Ifzliters of water is measurable, you must havezliters of water contained withinone or both bucketsby 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: Math, GCD(greatest common divisor)

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

        if not (x + y >= z):
            # because finally the z litres water will be contained in one or both jugs
            return False

        # Based on the 'Extended Euclidean algorithm':
        # a * m + b * n = d, if d = gcd(a, b), there must exist the pairs(m, n)
        # Based on 'Bezout's identity':
        # a * m + b * n = z, if d = gcd(a, b), and z is the times of d (z % d == 0), 
        # then there must exist the pairs of (m, n).
        x_y_gcd = self.gcd(x, y)
        return z % x_y_gcd == 0

    def gcd(self, a, b):
        # Based on 'Euclidean algorithm':
        # gcd(a, b) = gcd(b, a mod b)

        r = a % b

        # base case
        if r == 0:
            return b

        return self.gcd(b, r)

Revelation:

• Extended Euclidean algorithm: a * m + b * n = d, if d = gcd(a, b), there must exist the pair(m, n). reference: https://zh.wikipedia.org/wiki/扩展欧几里得算法
• Bezout's identity: a * m + b * n = z, if d = gcd(a, b) and z % d == 0, there must exist infinite pairs (m, n). reference: https://zh.wikipedia.org/wiki/貝祖等式

Note:

• Time complexity = O(lgy), the time complexity of the above algorithm depends on the time complexity of the gcd, and the time complexity of gcd = O(lgy), reference: https://zhaonanli.gitbooks.io/algorithm/content/gcd-greatest-common-divisor.html
• Euclidean Algorithm to calculate gcd, reference: https://zhaonanli.gitbooks.io/algorithm/content/gcd-greatest-common-divisor.html