Water jug problem (reach a target amount)
Problem
You have jugs of capacity m and n litres and unlimited water. Each step you may fill a jug, empty a jug, or pour one into the other until the source is empty or the target is full. Return the minimum number of steps to measure exactly d litres in either jug, or −1 if impossible.
Example 1
Input: m = 3, n = 5, d = 4 Output: 6
Also asked as: Water Jug problem using BFS
Test cases
Case 1
Input: 3, 5, 4 Expected: 6
Case 2
Input: 4, 3, 2 Expected: 4
Case 3
Input: 3, 5, 3 Expected: 1
Case 4
Input: 2, 6, 5 Expected: -1
View solutionHide solution1 approach
1. BFS over (jug1, jug2) states
Time O(cap1 · cap2)Space O(cap1 · cap2)
Each state is the pair of current amounts; transitions are fill/empty/pour for either jug. BFS finds the fewest steps to any state containing the target.
function waterJug(cap1, cap2, target) { const seen = new Set(['0,0']); let q = [[0, 0, 0]]; while (q.length) { const next = []; for (const [a, b, d] of q) { if (a === target || b === target || a + b === target) return d; const moves = [ [cap1, b], [a, cap2], [0, b], [a, 0], [Math.min(a + b, cap1), b - (Math.min(a + b, cap1) - a)], [a - (Math.min(a + b, cap2) - b), Math.min(a + b, cap2)], ]; for (const [na, nb] of moves) { const key = na + ',' + nb; if (!seen.has(key)) { seen.add(key); next.push([na, nb, d + 1]); } } } q = next; } return -1;}