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.

Examples

Example 1: (From the famous “Die Hard” example)

1
2


Input: x = 3, y = 5, z = 4
Output: True

Example 2:

1
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

1
2
3
4
5
6
7
8


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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


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
    }
}

1
2
3
4
5
6
7
8


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


#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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


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), where M and N are the jug capacities, since there are at most M*N possible 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


#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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


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);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


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)
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


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)
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


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), where M and N are the jug capacities, since there are at most M*N possible states.
🧺 Space complexity: O(M * N), for the memoization set.

Problem#

Examples#

Solution#

Method 1 - Mathematical Approach (Diophantine Equation)#

Intuition#

Approach#

Recurrence Relation#

Base Case#

Code#

Complexity#

Method 2 - Breadth-First Search (BFS) / Depth-First Search (DFS)#

Intuition#

Approach#

Recurrence Relation#

Base Case#

Code#

Complexity#

Method 3 - Recursion and Memoization#

Intuition#

Approach#

Recurrence Relation#

Base Case#

Code#

Complexity#

Problem

Examples

Solution

Method 1 - Mathematical Approach (Diophantine Equation)

Intuition

Approach

Recurrence Relation

Base Case

Code

Complexity

Method 2 - Breadth-First Search (BFS) / Depth-First Search (DFS)

Intuition

Approach

Recurrence Relation

Base Case

Code

Complexity

Method 3 - Recursion and Memoization

Intuition

Approach

Recurrence Relation

Base Case

Code

Complexity