Water and Jug Problem
Medium · Graphs · Explanation and code example
Capacity Bound and Greatest Common Divisor
How it works
Pouring between the two jugs can create amounts that are multiples of their greatest common divisor. A nonzero target is reachable exactly when it is such a multiple and does not exceed the combined capacity. Zero is reachable without pouring.
Steps
- Accept target zero.
- Reject targets above the sum of capacities.
- Check divisibility by gcd(capacity1, capacity2).
Complexity
- Time: O(log min(a, b)) for Euclid gcd.
- Space: O(1).
Things to watch for
- Check the combined capacity bound before divisibility.
- Handle target zero separately.
- The result allows water split across both jugs.
Python code example
from math import gcd
class Solution:
def canMeasureWater(
self,
jug1Capacity: int,
jug2Capacity: int,
targetCapacity: int,
) -> bool:
return (targetCapacity == 0 or
jug1Capacity + jug2Capacity >= targetCapacity and
targetCapacity % gcd(jug1Capacity, jug2Capacity) == 0)
C++ code example
class Solution {
public:
bool canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
return targetCapacity == 0 ||
jug1Capacity + jug2Capacity >= targetCapacity &&
targetCapacity % std::gcd(jug1Capacity, jug2Capacity) == 0;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.