Water and Jug Problem
Problem
Given two jugs of capacity x and y and a target z, can we measure exactly z liters? Allowed operations: fill, empty, pour between jugs.
x = 3, y = 5, target = 4truefrom math import gcd
def can_measure_water(x, y, target):
if target == 0:
return True
if x + y < target:
return False
return target % gcd(x, y) == 0function canMeasureWater(x, y, target) {
if (target === 0) return true;
if (x + y < target) return false;
const gcd = (a, b) => b === 0 ? a : gcd(b, a % b);
return target % gcd(x, y) === 0;
}class Solution {
public boolean canMeasureWater(int x, int y, int target) {
if (target == 0) return true;
if ((long)x + y < target) return false;
return target % gcd(x, y) == 0;
}
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
}bool canMeasureWater(int x, int y, int target) {
if (target == 0) return true;
if ((long)x + y < target) return false;
return target % __gcd(x, y) == 0;
}Explanation
Instead of simulating fills and pours, this solution uses a result from number theory called Bézout's identity. Every amount you can ever measure with two jugs is some combination a*x + b*y, and those combinations are exactly the multiples of gcd(x, y).
So the target is reachable when two things hold: the target is at most x + y (you can never hold more water than both jugs combined), and the target is a multiple of gcd(x, y), i.e. target % gcd(x, y) == 0. A target of 0 is trivially measurable.
The gcd is found with the quick Euclidean algorithm, which repeatedly replaces the pair with (b, a % b) until the second number hits zero.
Example: x = 3, y = 5, target = 4. Here gcd(3, 5) = 1, and 4 is a multiple of 1, while 4 <= 3 + 5. Both conditions hold, so the answer is true.
It works because pouring water around only ever adds or subtracts whole jug capacities, so you can never escape the multiples of their greatest common divisor.