# Time:  O(logn),  n is the max of (x, y)
# Space: O(1)

# 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.
#
# Operations allowed:
#
# Fill any of the jugs completely.
# 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:
#
# Input: x = 2, y = 6, z = 4
# Output: True
# Example 2:
#
# Input: x = 2, y = 6, z = 5
# Output: False

# Bézout's identity (also called Bézout's lemma) 
from fractions import gcd
class Solution(object):
    def canMeasureWater(self, x, y, z):
        """
        :type x: int
        :type y: int
        :type z: int
        :rtype: bool
        """
        # The problem is to solve:
        # - check z <= max(x, y) 
        # - check if there is any (a, b) integers s.t. ax + by = z
        return z <= max(x, y) and z % gcd(x, y) == 0

@@ -638,34 +638,8 @@
 a) %0A
-from fractions import gcd%0A
 clas
@@ -798,32 +798,136 @@
 ool%0A        %22%22%22%0A
+        def gcd(a, b):%0A            while b:%0A                a, b = b, a%25b%0A            return a%0A        %0A
         # The pr
@@ -963,31 +963,26 @@
 - check 
-z %3C= max(x, y) 
+x + y %3E= z
 %0A       
@@ -1062,25 +1062,35 @@
 n z 
-%3C= max(x, y
+== 0 or ((x + y %3E= z
 ) and 
+(
 z %25 
@@ -1103,9 +1103,11 @@
  y) == 0
+))
 %0A

Update water-and-jug-problem.py