Water and Jug
MediumUpdated: Aug 2, 2025
Practice on:
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.
Examples
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
Solution
Method 1 - Mathematical Approach (Diophantine Equation)
Intuition
The key insight is that the water jug problem can be reduced to a question about integer solutions: can we measure exactly z liters using jugs of size x and y? This is only possible if z is a multiple of the greatest common divisor (gcd) of x and y, and does not exceed the total capacity. This is a classic result from number theory (Diophantine equations).
Approach
We use the fact that it is possible to measure z liters if and only if z is a non-negative integer less than or equal to max(x, y) and z is divisible by gcd(x, y). This can be checked directly using the Euclidean algorithm for gcd.
Recurrence Relation
There is no recurrence in this direct mathematical approach, but the underlying principle is:
canMeasure(x, y, z) = (z <= max(x, y)) and (z % gcd(x, y) == 0)
Base Case
If z == 0, the answer is always true (no water needed).
Code
C++
class Solution {
public:
bool canMeasureWater(int x, int y, int z) {
if (z == 0) return true;
if (z > x + y) return false;
return z % std::gcd(x, y) == 0;
}
};
Go
func canMeasureWater(x int, y int, z int) bool {
if z == 0 {
return true
}
if z > x+y {
return false
}
return gcd(x, y) != 0 && z%gcd(x, y) == 0
}
func gcd(a, b int) int {
for b != 0 {
a, b = b, a%b
}
return a
}
Java
class Solution {
public boolean canMeasureWater(int x, int y, int z) {
if (z == 0) return true;
if (z > x + y) return false;
return z % gcd(x, y) == 0;
}
private int gcd(int a, int b) {
while (b != 0) {
int t = b;
b = a % b;
a = t;
}
return a;
}
}
Kotlin
class Solution {
fun canMeasureWater(x: Int, y: Int, z: Int): Boolean {
if (z == 0) return true
if (z > x + y) return false
return z % gcd(x, y) == 0
}
private fun gcd(a: Int, b: Int): Int {
var a = a
var b = b
while (b != 0) {
val t = b
b = a % b
a = t
}
return a
}
}
Python
class Solution:
def canMeasureWater(self, x: int, y: int, z: int) -> bool:
if z == 0:
return True
if z > x + y:
return False
from math import gcd
return z % gcd(x, y) == 0
Rust
impl Solution {
pub fn can_measure_water(x: i32, y: i32, z: i32) -> bool {
if z == 0 {
return true;
}
if z > x + y {
return false;
}
fn gcd(mut a: i32, mut b: i32) -> i32 {
while b != 0 {
let t = b;
b = a % b;
a = t;
}
a
}
z % gcd(x, y) == 0
}
}
TypeScript
class Solution {
canMeasureWater(x: number, y: number, z: number): boolean {
if (z === 0) return true;
if (z > x + y) return false;
return z % this.gcd(x, y) === 0;
}
private gcd(a: number, b: number): number {
while (b !== 0) {
const t = b;
b = a % b;
a = t;
}
return a;
}
}
Complexity
- ⏰ Time complexity:
O(log min(x, y)), because the gcd calculation uses the Euclidean algorithm. - 🧺 Space complexity:
O(1), since only a constant amount of extra space is used.
Method 2 - Breadth-First Search (BFS) / Depth-First Search (DFS)
Intuition
Instead of using number theory, we can treat the water jug problem as a state-space search. Each state is a pair (a, b) representing the amount of water in each jug. By applying all allowed operations, we can explore all possible states and check if any state reaches exactly z liters. BFS ensures we find the solution with the minimum number of steps.
Approach
We use BFS (or DFS) to explore all possible states, starting from (0, 0). At each step, we generate all possible next states by filling, emptying, or pouring between jugs. We use a set to avoid revisiting states. If we reach a state where either jug contains exactly z liters, we return true.
Recurrence Relation
Let canMeasure(a, b) be true if we can reach a state with z liters from state (a, b).
At each state, try all possible moves:
- Fill jug 1 or jug 2
- Empty jug 1 or jug 2
- Pour from jug 1 to jug 2, or jug 2 to jug 1
Base Case
If either jug contains exactly z liters, or their sum is z, return true.
Code
C++
#include <queue>
#include <set>
class Solution {
public:
bool canMeasureWater(int x, int y, int z) {
if (z == 0) return true;
if (z > x + y) return false;
std::queue<std::pair<int, int>> q;
std::set<std::pair<int, int>> visited;
q.push({0, 0});
while (!q.empty()) {
auto [a, b] = q.front(); q.pop();
if (a == z || b == z || a + b == z) return true;
if (visited.count({a, b})) continue;
visited.insert({a, b});
// Fill jug 1
q.push({x, b});
// Fill jug 2
q.push({a, y});
// Empty jug 1
q.push({0, b});
// Empty jug 2
q.push({a, 0});
// Pour jug 1 -> jug 2
int pour = std::min(a, y - b);
q.push({a - pour, b + pour});
// Pour jug 2 -> jug 1
pour = std::min(b, x - a);
q.push({a + pour, b - pour});
}
return false;
}
};
Go
func canMeasureWater(x int, y int, z int) bool {
if z == 0 {
return true
}
if z > x+y {
return false
}
type state struct{ a, b int }
visited := make(map[state]bool)
queue := []state{{0, 0}}
for len(queue) > 0 {
cur := queue[0]
queue = queue[1:]
a, b := cur.a, cur.b
if a == z || b == z || a+b == z {
return true
}
if visited[cur] {
continue
}
visited[cur] = true
queue = append(queue, state{x, b})
queue = append(queue, state{a, y})
queue = append(queue, state{0, b})
queue = append(queue, state{a, 0})
pour := min(a, y-b)
queue = append(queue, state{a - pour, b + pour})
pour = min(b, x-a)
queue = append(queue, state{a + pour, b - pour})
}
return false
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
Java
import java.util.*;
class Solution {
public boolean canMeasureWater(int x, int y, int z) {
if (z == 0) return true;
if (z > x + y) return false;
Queue<int[]> queue = new LinkedList<>();
Set<String> visited = new HashSet<>();
queue.offer(new int[]{0, 0});
while (!queue.isEmpty()) {
int[] cur = queue.poll();
int a = cur[0], b = cur[1];
if (a == z || b == z || a + b == z) return true;
String key = a + "," + b;
if (visited.contains(key)) continue;
visited.add(key);
queue.offer(new int[]{x, b});
queue.offer(new int[]{a, y});
queue.offer(new int[]{0, b});
queue.offer(new int[]{a, 0});
int pour = Math.min(a, y - b);
queue.offer(new int[]{a - pour, b + pour});
pour = Math.min(b, x - a);
queue.offer(new int[]{a + pour, b - pour});
}
return false;
}
}
Kotlin
import java.util.*
class Solution {
fun canMeasureWater(x: Int, y: Int, z: Int): Boolean {
if (z == 0) return true
if (z > x + y) return false
val queue: Queue<Pair<Int, Int>> = LinkedList()
val visited = mutableSetOf<Pair<Int, Int>>()
queue.offer(0 to 0)
while (queue.isNotEmpty()) {
val (a, b) = queue.poll()
if (a == z || b == z || a + b == z) return true
if (visited.contains(a to b)) continue
visited.add(a to b)
queue.offer(x to b)
queue.offer(a to y)
queue.offer(0 to b)
queue.offer(a to 0)
val pour1 = minOf(a, y - b)
queue.offer((a - pour1) to (b + pour1))
val pour2 = minOf(b, x - a)
queue.offer((a + pour2) to (b - pour2))
}
return false
}
}
Python
from collections import deque
class Solution:
def canMeasureWater(self, x: int, y: int, z: int) -> bool:
if z == 0:
return True
if z > x + y:
return False
queue = deque([(0, 0)])
visited = set()
while queue:
a, b = queue.popleft()
if a == z or b == z or a + b == z:
return True
if (a, b) in visited:
continue
visited.add((a, b))
queue.append((x, b))
queue.append((a, y))
queue.append((0, b))
queue.append((a, 0))
pour = min(a, y - b)
queue.append((a - pour, b + pour))
pour = min(b, x - a)
queue.append((a + pour, b - pour))
return False
Rust
use std::collections::{HashSet, VecDeque};
impl Solution {
pub fn can_measure_water(x: i32, y: i32, z: i32) -> bool {
if z == 0 {
return true;
}
if z > x + y {
return false;
}
let mut queue = VecDeque::new();
let mut visited = HashSet::new();
queue.push_back((0, 0));
while let Some((a, b)) = queue.pop_front() {
if a == z || b == z || a + b == z {
return true;
}
if visited.contains(&(a, b)) {
continue;
}
visited.insert((a, b));
queue.push_back((x, b));
queue.push_back((a, y));
queue.push_back((0, b));
queue.push_back((a, 0));
let pour1 = std::cmp::min(a, y - b);
queue.push_back((a - pour1, b + pour1));
let pour2 = std::cmp::min(b, x - a);
queue.push_back((a + pour2, b - pour2));
}
false
}
}
TypeScript
class Solution {
canMeasureWater(x: number, y: number, z: number): boolean {
if (z === 0) return true;
if (z > x + y) return false;
const queue: [number, number][] = [[0, 0]];
const visited = new Set<string>();
while (queue.length) {
const [a, b] = queue.shift()!;
if (a === z || b === z || a + b === z) return true;
const key = `${a},${b}`;
if (visited.has(key)) continue;
visited.add(key);
queue.push([x, b]);
queue.push([a, y]);
queue.push([0, b]);
queue.push([a, 0]);
let pour = Math.min(a, y - b);
queue.push([a - pour, b + pour]);
pour = Math.min(b, x - a);
queue.push([a + pour, b - pour]);
}
return false;
}
}
Complexity
- ⏰ Time complexity:
O(M * N), whereMandNare the jug capacities, since there are at mostM*Npossible states. - 🧺 Space complexity:
O(M * N), for the visited set and queue.
Method 3 - Recursion and Memoization
Intuition
This approach explores all possible states using recursion, but avoids redundant work by memoizing results for each state. At each step, we try all allowed operations (fill, empty, pour) and recursively check if we can reach the target. Memoization ensures we do not revisit the same state multiple times.
Approach
We define a recursive function that, given the current amount in each jug, tries all possible moves and checks if the target can be reached. We use a set or map to memoize visited states. The recursion continues until either jug contains exactly z liters, or all possibilities are exhausted.
Recurrence Relation
Let canMeasure(a, b) be true if we can reach a state with z liters from state (a, b).
At each state, try all possible moves:
- Fill jug 1 or jug 2
- Empty jug 1 or jug 2
- Pour from jug 1 to jug 2, or jug 2 to jug 1
Base Case
If either jug contains exactly z liters, or their sum is z, return true.
Code
C++
#include <unordered_set>
#include <string>
class Solution {
public:
bool canMeasureWater(int x, int y, int z) {
std::unordered_set<std::string> memo;
return dfs(x, y, z, 0, 0, memo);
}
bool dfs(int x, int y, int z, int a, int b, std::unordered_set<std::string>& memo) {
std::string key = std::to_string(a) + "," + std::to_string(b);
if (memo.count(key)) return false;
if (a == z || b == z || a + b == z) return true;
memo.insert(key);
// Fill jug 1
if (dfs(x, y, z, x, b, memo)) return true;
// Fill jug 2
if (dfs(x, y, z, a, y, memo)) return true;
// Empty jug 1
if (dfs(x, y, z, 0, b, memo)) return true;
// Empty jug 2
if (dfs(x, y, z, a, 0, memo)) return true;
// Pour jug 1 -> jug 2
int pour = std::min(a, y - b);
if (dfs(x, y, z, a - pour, b + pour, memo)) return true;
// Pour jug 2 -> jug 1
pour = std::min(b, x - a);
if (dfs(x, y, z, a + pour, b - pour, memo)) return true;
return false;
}
};
Go
func canMeasureWater(x int, y int, z int) bool {
memo := make(map[[2]int]bool)
var dfs func(a, b int) bool
dfs = func(a, b int) bool {
if memo[[2]int{a, b}] {
return false
}
if a == z || b == z || a+b == z {
return true
}
memo[[2]int{a, b}] = true
return dfs(x, b) || dfs(a, y) || dfs(0, b) || dfs(a, 0) ||
dfs(a-min(a, y-b), b+min(a, y-b)) || dfs(a+min(b, x-a), b-min(b, x-a))
}
return dfs(0, 0)
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
Java
import java.util.*;
class Solution {
public boolean canMeasureWater(int x, int y, int z) {
Set<String> memo = new HashSet<>();
return dfs(x, y, z, 0, 0, memo);
}
private boolean dfs(int x, int y, int z, int a, int b, Set<String> memo) {
String key = a + "," + b;
if (memo.contains(key)) return false;
if (a == z || b == z || a + b == z) return true;
memo.add(key);
return dfs(x, y, z, x, b, memo) ||
dfs(x, y, z, a, y, memo) ||
dfs(x, y, z, 0, b, memo) ||
dfs(x, y, z, a, 0, memo) ||
dfs(x, y, z, a - Math.min(a, y - b), b + Math.min(a, y - b), memo) ||
dfs(x, y, z, a + Math.min(b, x - a), b - Math.min(b, x - a), memo);
}
}
Kotlin
import java.util.*
class Solution {
fun canMeasureWater(x: Int, y: Int, z: Int): Boolean {
val memo = mutableSetOf<Pair<Int, Int>>()
fun dfs(a: Int, b: Int): Boolean {
if (memo.contains(a to b)) return false
if (a == z || b == z || a + b == z) return true
memo.add(a to b)
return dfs(x, b) || dfs(a, y) || dfs(0, b) || dfs(a, 0) ||
dfs(a - minOf(a, y - b), b + minOf(a, y - b)) ||
dfs(a + minOf(b, x - a), b - minOf(b, x - a))
}
return dfs(0, 0)
}
}
Python
class Solution:
def canMeasureWater(self, x: int, y: int, z: int) -> bool:
memo = set()
def dfs(a, b):
if (a, b) in memo:
return False
if a == z or b == z or a + b == z:
return True
memo.add((a, b))
return (
dfs(x, b) or dfs(a, y) or dfs(0, b) or dfs(a, 0) or
dfs(a - min(a, y - b), b + min(a, y - b)) or
dfs(a + min(b, x - a), b - min(b, x - a))
)
return dfs(0, 0)
Rust
use std::collections::HashSet;
impl Solution {
pub fn can_measure_water(x: i32, y: i32, z: i32) -> bool {
fn dfs(x: i32, y: i32, z: i32, a: i32, b: i32, memo: &mut HashSet<(i32, i32)>) -> bool {
if memo.contains(&(a, b)) {
return false;
}
if a == z || b == z || a + b == z {
return true;
}
memo.insert((a, b));
let pour1 = std::cmp::min(a, y - b);
let pour2 = std::cmp::min(b, x - a);
dfs(x, y, z, x, b, memo) ||
dfs(x, y, z, a, y, memo) ||
dfs(x, y, z, 0, b, memo) ||
dfs(x, y, z, a, 0, memo) ||
dfs(x, y, z, a - pour1, b + pour1, memo) ||
dfs(x, y, z, a + pour2, b - pour2, memo)
}
let mut memo = HashSet::new();
dfs(x, y, z, 0, 0, &mut memo)
}
}
TypeScript
class Solution {
canMeasureWater(x: number, y: number, z: number): boolean {
const memo = new Set<string>();
function dfs(a: number, b: number): boolean {
const key = `${a},${b}`;
if (memo.has(key)) return false;
if (a === z || b === z || a + b === z) return true;
memo.add(key);
return (
dfs(x, b) || dfs(a, y) || dfs(0, b) || dfs(a, 0) ||
dfs(a - Math.min(a, y - b), b + Math.min(a, y - b)) ||
dfs(a + Math.min(b, x - a), b - Math.min(b, x - a))
);
}
return dfs(0, 0);
}
}
Complexity
- ⏰ Time complexity:
O(M * N), whereMandNare the jug capacities, since there are at mostM*Npossible states. - 🧺 Space complexity:
O(M * N), for the memoization set.