Water Jug problem using BFS Hard 0 attempts
GeeksforGeeks ↗

Water Jug problem using BFS

Hard GraphBFSDFS GeeksforGeeks

You have two unmarked jugs with capacities x and y litres. Using the standard moves — filling a jug to the top, emptying a jug completely, or pouring from one jug into the other until the source empties or the destination fills — work out whether you can end up with exactly target litres in either jug or across both jugs combined. Solve it by exploring the reachable (jug1, jug2) states with BFS.

Input Format
Implement canMeasureWater(x, y, target). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
x = 3
y = 5
target = 4
Output
true

Example 2

Input
x = 2
y = 6
target = 5
Output
false

Example 3

Input
x = 3
y = 5
target = 8
Output
true
Constraints
  • 1 <= x, y <= 10^6
  • 0 <= target <= 10^6
Test Cases (3)
Case 1
Args: [3,5,4] Expected: true
Case 2
Args: [2,6,5] Expected: false
Case 3
Args: [3,5,8] Expected: true
Topics
GraphBFSDFS

BFS on States

javascript
function canMeasureWater(x, y, target) {
  if (target > x + y) return false;
  const visited = new Set(), q = [[0, 0]];
  visited.add('0,0');
  let head = 0;
  while (head < q.length) {
    const [a, b] = q[head++];
    if (a===target||b===target||a+b===target) return true;
    const states = [[x,b],[a,y],[0,b],[a,0],
      [a-Math.min(a,y-b), b+Math.min(a,y-b)],
      [a+Math.min(b,x-a), b-Math.min(b,x-a)]];
    for (const [na,nb] of states) {
      const key = na+','+nb;
      if (!visited.has(key)) { visited.add(key); q.push([na,nb]); }
    }
  }
  return false;
}

Time: O(x × y) | Space: O(x × y)

Saved in this browser only. Private to you.

JavaScript