Leetcode 365. Water and Jug Problem

Problem Explanation

We are given two jugs with different capacities, and the challenge is to measure a specific amount of liters (z liters) using these jugs under specific operations:

• Fill any jug completely.
• Empty any jug.
• Pour water from one jug to another until the one being filled is completely full, or the first one is empty.

To solve this problem, we can use the mathematical concept of Bezout's Identity, which states that the weights of a solution to the linear Diophantine equation ax + by = d will always be a multiple of the greatest common divisor (gcd) of a and b.

If z liters of water is measurable, you can adjust to meet the necessary amount exactly with these two jugs. In other words, z must be a multiple of the gcd of x and y.

The code above also covers the edge case where z may be equal to zero. If z equals to zero, the function should return 'True' as it is always possible to empty the jugs.

Let's consider the example where x = 3, y = 5, z = 4. According to the problem statement, it is possible to measure exactly 4 liters as 4 % gcd(3, 5) = 4 % 1 = 0.

Python Solution

1
2python
3class Solution:
4    def canMeasureWater(self, x, y, z):
5        import math
6            
7        # Case where z equals zero
8        if z == 0:
9            return True
10
11        # Cases where z can be measured with x and y jugs
12        if x + y >= z and z % math.gcd(x, y) == 0:
13            return True
14            
15        return False

Java Solution

1
2java
3class Solution {
4    public boolean canMeasureWater(int x, int y, int z) {
5        // Case where z equals zero
6        if (z == 0) {
7            return true;
8        }
9        
10        // Cases where z can be measured with x and y jugs
11        if (x + y >= z && z % gcd(x, y) == 0) {
12            return true;
13        }
14        
15        return false;
16    }
17  
18    // function to find gcd
19    public int gcd(int a, int b){
20        while(b != 0 ){
21            int temp = b;
22            b = a % b;  // % is remainder
23            a = temp;
24        }
25        return a;
26    }
27}

JavaScript Solution

1
2javascript
3class Solution {
4  canMeasureWater(x, y, z) {
5    const gcd = (a, b) => (b === 0 ? a : gcd(b, a % b));
6
7    // Case where z equals zero
8    if (z === 0) {
9      return true;
10    }
11    
12    // Cases where z can be measured with x and y jugs
13    if (x + y >= z && z % gcd(x, y) === 0) {
14      return true;
15    }
16    
17    return false;
18  }
19}

C++ Solution

1
2cpp
3class Solution {
4public:
5    bool canMeasureWater(int x, int y, int z) {
6        // Case where z equals zero
7        if (z == 0) {
8            return true;
9        }
10        
11        // Cases where z can be measured with x and y jugs
12        if (x + y >= z && z % gcd(x, y) == 0) {
13            return true;
14        }
15        
16        return false;
17    }
18  
19    // function to find gcd
20    int gcd(int a, int b) {
21        while (b != 0) {
22            int temp = b;
23            b = a % b;
24            a = temp;
25        }
26        return a;
27    }
28};

C# Solution

1
2csharp
3public class Solution {
4    public bool CanMeasureWater(int x, int y, int z) {
5        // Case where z equals zero
6        if (z == 0) {
7            return true;
8        }
9        
10        // Cases where z can be measured with x and y jugs
11        if (x + y >= z && z % GCD(x, y) == 0) {
12            return true;
13        }
14        
15        return false;
16    }
17    
18    // function to find gcd
19    private int GCD(int a, int b) {
20        while (b != 0) {
21            int temp = b;
22            b = a % b;
23            a = temp;
24        }
25        return a;
26    }
27}

Remember, these solutions are built on the assumption that measuring water, filling or emptying jugs are not costly operations.In reality, finding the gcd may require extensive computation if x and y are large. The complexity of all solutions is O(log(min(x, y)) due to the GCD calculation.

Python Async/Sync Variant

The Python solution can be written in either an asynchronous or a synchronous manner as shown below:

1
2python
3import asyncio
4import math
5
6class AsyncSolution:
7    async def canMeasureWater(self, x, y, z):
8        # Case where z equals zero
9        if z == 0:
10            return True
11        if x==0 or y==0:
12            return ((x+y)==z)
13        # Cases where z can be measured with x and y jugs
14        if x + y >= z and z % math.gcd(x, y) == 0:
15            return True
16        return False
17
18class SyncSolution:
19    def canMeasureWater(self, x, y, z):
20        # Case where z equals zero
21        if z == 0:
22            return True
23        if x==0 or y==0:
24            return ((x+y)==z)
25        # Cases where z can be measured with x and y jugs
26        if x + y >= z and z % math.gcd(x, y) == 0:
27            return True
28        return False

These solutions can handle even larger numbers and work with both synchronous and asynchronous Python code.

In conclusion, the problem of measuring a specific amount of water using two jugs can be solved using Bezout's Identity and finding the gcd of the capacities of the two jugs. The solutions can be implemented in various programming languages like Python, Java, JavaScript, C++, and C#. The complexity of the solutions is O(log(min(x,y))) due to the gcd computation. The solutions assume water measurement, filling or emptying jugs are not costly operations, and handle cases where the desired amount of water is zero or is more than the total capacity of both jugs.