Question
Formatted question description: https://leetcode.ca/all/365.html
365 Water and Jug Problem
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.
If z liters of water is measurable, you must have z liters of water contained within one or both buckets by the end.
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.
Example 1: (From the famous "Die Hard" example)
Input: x = 3, y = 5, z = 4
Output: True
Example 2:
Input: x = 2, y = 6, z = 5
Output: False
Algorithm
This question can actually be converted to a very large container. We have two cups with capacities x and y respectively. Ask us whether we can make the container by pouring water in and scooping out with two cups. The water in it is exactly z liters. Then we can use a formula to express:
z = m * x + n * y
Where m, n are the times of scooping and pouring water, a positive number means to scoop water in, and a negative number to pour water out.
Then the example in the title can be written as: 4 = (-2) * 3 + 2 * 5, that is, a 3 liter pitcher is poured out twice, and a 5 liter pitcher is scooped twice.
Then the question becomes for any given x, y, z, whether there are m and n that make the above equation hold.
According to the theorem of Bézout’s identity, the solution of ax + by = d is d = gcd(x, y), then as long as z% d == 0, the above equation will be solved, so the problem will be solved. .
We just need to see if z is a multiple of the greatest common divisor of x and y.
Don’t forget that there is a restriction x + y >= z, because x and y cannot weigh more water than their sum.
Code
Java
public class Water_and_Jug_Problem {
class Solution {
public boolean canMeasureWater(int x, int y, int z) {
return z == 0 || (x + y >= z && z % gcd(x, y) == 0);
}
// Bézout's identity
int gcd(int x, int y) {
return y == 0 ? x : gcd(y, x % y);
}
}
}