# Solution using modular arithmetic

• 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
``````

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