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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.