Water And Jug Problem - Leetcode Solution

The Water and Jug Problem is a classic math problem, given two jugs with capacities X and Y, and a target capacity Z. The goal is to determine whether it is possible to measure exactly Z liters using only these two jugs. In this problem, we assume that both jugs are initially empty and that we have an unlimited supply of water.

A more formal statement of the problem is:

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 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.

We can solve this problem using the concept of gcd (greatest common divisor). The key observation is that we can obtain any amount of water that is a multiple of gcd(x, y) using only these two jugs. Therefore, the problem is solvable if and only if z is a multiple of gcd(x, y).

With these observations, the solution is straightforward. We first check if z is zero or if z is greater than the sum of our jug capacities. If either of these cases is true, then we cannot measure exactly z litres, and we return False.

If z is a multiple of the gcd(x, y), then we can measure exactly z litres by filling the smaller jug (x or y) and pouring it into the larger jug (y or x) until we get a total of z litres in one of the jugs. If z is not a multiple of the gcd(x, y), then we cannot measure exactly z litres, and we return False.

Now, we need to write a function that calculates the gcd of x and y. We can use the Euclidean algorithm, which is a recursive algorithm to compute the gcd of two numbers. Here is the function to calculate the gcd:

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

With this function, we can write our solution:

def canMeasureWater(x: int, y: int, z: int) -> bool:
    if z == 0:
        return True
    if x + y < z:
        return False
    if x == 0 or y == 0:
        return z == x or z == y
    
    # calculate gcd of x and y
    g = gcd(x, y)
    
    # check if z is a multiple of g
    return z % g == 0

Time Complexity:

The Euclidean algorithm takes O(log(min(x, y))) time to calculate the gcd of x and y. Therefore, the time complexity of our solution is O(log(min(x, y))).

Space Complexity:

The space complexity of our solution is O(1), as we are not using any extra data structures.

1