Solution using modular arithmetic


  • 0

    First we borrow a fact from basic group theory about sets of integers mod y: The set {x mod y, x + x mod y, x + x + x mod y, ...} is equal to the set {d, d + d, ..., d + .. + d} where d = gcd(x, y) and the last sum is the largest we can get without surpassing y. Now suppose that we have some solution to the problem for a given x, y, and z. Without loss of generality, assume that y > x. Then we can pour out as much water as we can from the y jug to the x jug, until either the y jug is empty or the x jug is full. If the y jug is empty, then this means that we can fit everything into the y jug, so we just pour all of the water back into the y jug. Thus, either way, we have rearranged the water in the jugs such that either the x jug is empty or the x jug is full. Now, know this, we know that if the set {x mod y, x + x mod y, ...} contains z or z - x, then we are done, because we can generate everything in this set by pouring x into y over and over again, and possibly emptying y and refilling it with what is leftover in x if y gets full. Our algorithm checks for this condition with the trick stated above by computing d = gcd(x, y) and then seeing if z is a multiple of d. On the other hand, one must realize that the only numbers we can get from our given operations are the numbers inside of the set {x mod y, x + x mod y, ...}. Thus a solution exists if and only if z or z - x is inside of {d, d+d, ..., d + .. + d}, which is true if and only if z %d == 0.

    class Solution:
        def canMeasureWater(self, x, y, z):
            """
            :type x: int
            :type y: int
            :type z: int
            :rtype: bool
            """
            def gcd(a, b):
                if b == 0:
                    return a
                else:
                    return gcd(b, a % b)
            if x ==0 and y ==0:
                if z == 0:
                    return True
                else:
                    return False
            if z > x + y:
                return False
            a = max(x, y)
            b = min(x, y)
            d = gcd(a, b)
            if z % d == 0:
                return True
            else:
                return False
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.