[LeetCode] 365. Water and Jug Problem

 Problem : https://leetcode.com/problems/water-and-jug-problem/

This problem equals to consider there is a large container, use the 2 jugs to pour water into the container or take water out of the container, and end up with z liters water in the container.

a * x + b * y = z

Positive a / b means pour water into the container.

Negative a / b means take water out of the container.

According to Bézout's identity :  a * x + b * y =  GCD( x, y )

GCD : greatest common divisor of x and y.

So, we can get the needed liters of water when GCD( x, y ) % z == 0.

class Solution:
    def canMeasureWater(self, x: int, y: int, z: int) -> bool:
        
        def gcd(a, b):
            if a != 0:
                return gcd(b%a, a)
            else:
                return b

        if x > y:
            x, y = y, x
            
        
        return z == 0 or z <= (x + y) and y > 0 and z % gcd(x, y) == 0