Water and Jug Problem — Solution in Python, Java & C++
Water and Jug Problem solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Water and Jug Problem is a medium coding problem on math, depth-first search and breadth-first search, asked in Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Math, Depth-First Search, Breadth-First Search
- Asked at: Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You have two empty jugs holding up to x and y litres, and an unlimited tap. The allowed operations are:
- fill either jug to the brim;
- empty either jug completely;
- pour from one jug into the other until the receiving jug is full or the pouring jug is empty.
Return true if, after some sequence of operations, the total amount of water in the two jugs can be exactly target litres.
Example 1
Input: x = 3, y = 5, target = 4
Output: true
Explanation: Fill the 5, pour into the 3 (leaving 2), empty the 3, pour the 2 across, fill the 5, top the 3 up from it (leaving 4 in the 5-litre jug), then empty the 3: 4 litres in total.
Example 2
Input: x = 4, y = 6, target = 7
Output: false
Explanation: Every amount you can ever hold is even.
Example 3
Input: x = 1, y = 2, target = 3
Output: true
Constraints
1 <= x, y, target <= 1000
Hints for Water and Jug Problem
Hint 1
Think of the total amount of water. Each operation changes the total by
x, byy, or not at all.Hint 2
So any total you can reach is a combination
a*x + b*y— which totals of that form are actually reachable without exceeding the jugs?Hint 3
By Bézout's identity, the reachable totals are exactly the multiples of
gcd(x, y)that do not exceedx + y.
How to solve Water and Jug Problem
The reachable totals are exactly the multiples of gcd(x, y) between 0 and x + y.
Approach
- If
target > x + y, the jugs cannot hold it: returnfalse. - Compute
g = gcd(x, y)with the Euclidean algorithm. - Return whether
targetis a multiple ofg.
Why it works
Every operation either leaves the total unchanged (pouring) or adds or removes a full jug's worth (x or y), so every reachable total is an integer combination of x and y — a multiple of g. Conversely, repeatedly filling one jug and pouring it into the other, emptying the other whenever it is full, walks through the residues k*x mod y and produces every multiple of g up to y in one jug; adding a full second jug covers the rest up to x + y. That is Bézout's identity made concrete, and the BFS over all states agrees with it.
Complexity
- Time —
O(log min(x, y)) - Space —
O(1)
Pitfalls
- The target is the total in both jugs, not the content of one jug.
- Forgetting the
target <= x + ybound: 10 is a multiple of gcd(3, 5) but does not fit. - A full BFS over (x+1)(y+1) states works but costs a million states at the upper limit.
Reference solution
Python
def canMeasureWater(x: int, y: int, target: int) -> bool:
if target > x + y:
return False
a, b = x, y
while b:
a, b = b, a % b
return target % a == 0Java
public static boolean canMeasureWater(int x, int y, int target) {
if (target > x + y) return false;
int a = x, b = y;
while (b != 0) {
int t = a % b;
a = b;
b = t;
}
return target % a == 0;
}C++
bool canMeasureWater(int x, int y, int target) {
if (target > x + y) return false;
int a = x, b = y;
while (b != 0) {
int t = a % b;
a = b;
b = t;
}
return target % a == 0;
}JavaScript
var canMeasureWater = function(x, y, target) {
if (target > x + y) return false;
var a = x, b = y;
while (b !== 0) {
var t = a % b;
a = b;
b = t;
}
return target % a === 0;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 337 math problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)