Breadth-First Search (BFS) Approach
The Breadth-First Search (BFS) algorithm can be used to solve the Water Jug problem by exploring all possible states of the jugs until the target quantity is reached. BFS is a graph traversal algorithm that visits all the neighboring states before moving to the next level.
Here's how the BFS approach works for the Water Jug problem:
1. Create a queue to store the states of the jugs.
2. Initialize the queue with the initial state (0, 0), representing empty jugs.
3. While the queue is not empty, do the following:
- Dequeue a state from the queue.
- If the dequeued state matches the target quantity, return the solution path.
- Generate all possible next states from the current state by applying the allowed operations (fill, empty, pour).
- Enqueue the new states if they haven't been visited before.
- Mark the current state as visited to avoid revisiting it.
4. If the queue becomes empty and the target quantity is not reached, there is no solution.
The BFS approach guarantees finding the shortest path to the target quantity, as it explores all possible states level by level.
Let's look at an example with the problem statement (3, 5, 4). The BFS approach will start with the initial state (0, 0) and explore the neighboring states by filling, emptying, and pouring water between the jugs until the state (4, 0) or (1, 4) is reached, indicating that 4 liters of water have been measured.
Note: The BFS approach is effective for solving the Water Jug problem, but it can be memory-intensive for large jug capacities as it needs to store all the visited states.
C++
#include <iostream>
#include <queue>
#include <map>
#include <vector>
using namespace std;
struct State {
int x, y;
vector<pair<int, int>> path;
State(int _x, int _y) : x(_x), y(_y) {}
};
bool bfs(int a, int b, int target) {
map<pair<int, int>, bool> visited;
queue<State> q;
q.push(State(0, 0));
visited[{0, 0}] = true;
while (!q.empty()) {
State current = q.front();
q.pop();
if (current.x == target || current.y == target) {
cout << "Path to reach the target:" << endl;
for (auto state : current.path) {
cout << "(" << state.first << ", " << state.second << ")" << endl;
}
return true;
}
// Fill jug 1
if (!visited[{a, current.y}]) {
State newState(a, current.y);
newState.path = current.path;
newState.path.push_back({a, current.y});
q.push(newState);
visited[{a, current.y}] = true;
}
// Fill jug 2
if (!visited[{current.x, b}]) {
State newState(current.x, b);
newState.path = current.path;
newState.path.push_back({current.x, b});
q.push(newState);
visited[{current.x, b}] = true;
}
// Empty jug 1
if (!visited[{0, current.y}]) {
State newState(0, current.y);
newState.path = current.path;
newState.path.push_back({0, current.y});
q.push(newState);
visited[{0, current.y}] = true;
}
// Empty jug 2
if (!visited[{current.x, 0}]) {
State newState(current.x, 0);
newState.path = current.path;
newState.path.push_back({current.x, 0});
q.push(newState);
visited[{current.x, 0}] = true;
}
// Pour from jug 1 to jug 2
int pour = min(current.x, b - current.y);
if (!visited[{current.x - pour, current.y + pour}]) {
State newState(current.x - pour, current.y + pour);
newState.path = current.path;
newState.path.push_back({current.x - pour, current.y + pour});
q.push(newState);
visited[{current.x - pour, current.y + pour}] = true;
}
// Pour from jug 2 to jug 1
pour = min(current.y, a - current.x);
if (!visited[{current.x + pour, current.y - pour}]) {
State newState(current.x + pour, current.y - pour);
newState.path = current.path;
newState.path.push_back({current.x + pour, current.y - pour});
q.push(newState);
visited[{current.x + pour, current.y - pour}] = true;
}
}
return false;
}
int main() {
int a = 3, b = 5, target = 4;
if (!bfs(a, b, target)) {
cout << "No solution exists!" << endl;
}
return 0;
}
You can also try this code with Online C++ Compiler
Java
import java.util.*;
class State {
int x, y;
List<int[]> path;
State(int x, int y) {
this.x = x;
this.y = y;
this.path = new ArrayList<>();
}
}
public class WaterJugBFS {
public static boolean bfs(int a, int b, int target) {
Set<String> visited = new HashSet<>();
Queue<State> queue = new LinkedList<>();
State initialState = new State(0, 0);
queue.offer(initialState);
visited.add("0,0");
while (!queue.isEmpty()) {
State current = queue.poll();
if (current.x == target || current.y == target) {
System.out.println("Path to reach the target:");
for (int[] state : current.path) {
System.out.println("(" + state[0] + ", " + state[1] + ")");
}
return true;
}
// Fill jug 1
if (!visited.contains(a + "," + current.y)) {
State newState = new State(a, current.y);
newState.path.addAll(current.path);
newState.path.add(new int[]{a, current.y});
queue.offer(newState);
visited.add(a + "," + current.y);
}
// Fill jug 2
if (!visited.contains(current.x + "," + b)) {
State newState = new State(current.x, b);
newState.path.addAll(current.path);
newState.path.add(new int[]{current.x, b});
queue.offer(newState);
visited.add(current.x + "," + b);
}
// Empty jug 1
if (!visited.contains("0," + current.y)) {
State newState = new State(0, current.y);
newState.path.addAll(current.path);
newState.path.add(new int[]{0, current.y});
queue.offer(newState);
visited.add("0," + current.y);
}
// Empty jug 2
if (!visited.contains(current.x + ",0")) {
State newState = new State(current.x, 0);
newState.path.addAll(current.path);
newState.path.add(new int[]{current.x, 0});
queue.offer(newState);
visited.add(current.x + ",0");
}
// Pour from jug 1 to jug 2
int pour = Math.min(current.x, b - current.y);
if (!visited.contains((current.x - pour) + "," + (current.y + pour))) {
State newState = new State(current.x - pour, current.y + pour);
newState.path.addAll(current.path);
newState.path.add(new int[]{current.x - pour, current.y + pour});
queue.offer(newState);
visited.add((current.x - pour) + "," + (current.y + pour));
}
// Pour from jug 2 to jug 1
pour = Math.min(current.y, a - current.x);
if (!visited.contains((current.x + pour) + "," + (current.y - pour))) {
State newState = new State(current.x + pour, current.y - pour);
newState.path.addAll(current.path);
newState.path.add(new int[]{current.x + pour, current.y - pour});
queue.offer(newState);
visited.add((current.x + pour) + "," + (current.y - pour));
}
}
return false;
}
public static void main(String[] args) {
int a = 3, b = 5, target = 4;
if (!bfs(a, b, target)) {
System.out.println("No solution exists!");
}
}
}
You can also try this code with Online Java Compiler
Python
from collections import deque
def bfs(a, b, target):
visited = set()
queue = deque()
initial_state = (0, 0)
queue.append((initial_state, []))
visited.add(initial_state)
while queue:
current_state, path = queue.popleft()
x, y = current_state
if x == target or y == target:
print("Path to reach the target:")
for state in path:
print(state)
return True
# Fill jug 1
if (a, y) not in visited:
new_state = (a, y)
new_path = path + [new_state]
queue.append((new_state, new_path))
visited.add(new_state)
# Fill jug 2
if (x, b) not in visited:
new_state = (x, b)
new_path = path + [new_state]
queue.append((new_state, new_path))
visited.add(new_state)
# Empty jug 1
if (0, y) not in visited:
new_state = (0, y)
new_path = path + [new_state]
queue.append((new_state, new_path))
visited.add(new_state)
# Empty jug 2
if (x, 0) not in visited:
new_state = (x, 0)
new_path = path + [new_state]
queue.append((new_state, new_path))
visited.add(new_state)
# Pour from jug 1 to jug 2
pour = min(x, b - y)
if (x - pour, y + pour) not in visited:
new_state = (x - pour, y + pour)
new_path = path + [new_state]
queue.append((new_state, new_path))
visited.add(new_state)
# Pour from jug 2 to jug 1
pour = min(y, a - x)
if (x + pour, y - pour) not in visited:
new_state = (x + pour, y - pour)
new_path = path + [new_state]
queue.append((new_state, new_path))
visited.add(new_state)
return False
if __name__ == "__main__":
a = 3
b = 5
target = 4
if not bfs(a, b, target):
print("No solution exists!")
You can also try this code with Online Python Compiler
Output
Path to reach the target:
(0, 5)
(3, 2)
(0, 2)
(2, 0)
(2, 5)
(3, 4)
Mathematical Approach
Apart from the BFS approach, we can also solve the Water Jug problem using a mathematical approach. This approach is based on the concept of the greatest common divisor (GCD) of the jug capacities.
The mathematical approach works in:
1. Check if the target quantity is a multiple of the GCD of the jug capacities.
- If yes, the problem has a solution.
- If no, the problem has no solution.
2. If the problem has a solution, perform the following steps:
- Initialize the amounts of water in both jugs to 0.
- Repeatedly fill the smaller jug & pour its contents into the larger jug until the target quantity is reached.
- If the larger jug becomes full, empty it & continue the process.
The mathematical approach is based on the following theorem:
- If the target quantity is a multiple of the GCD of the jug capacities, then the problem has a solution.
- The solution can be obtained by repeatedly filling the smaller jug & pouring its contents into the larger jug until the target quantity is reached.
Let's consider an example with the problem statement (3, 5, 4). The GCD of 3 & 5 is 1, & 4 is a multiple of 1. Therefore, the problem has a solution.
To solve the problem using the mathematical approach:
1. Initialize the amounts of water in both jugs to 0.
2. Fill the smaller jug (capacity 3) & pour its contents into the larger jug (capacity 5).
3. Fill the smaller jug again & pour its contents into the larger jug. Now, the larger jug contains 1 liter of water.
4. Empty the larger jug & pour the 1 liter of water from the smaller jug into the larger jug.
5. Fill the smaller jug & pour its contents into the larger jug. The larger jug now contains 4 liters of water, which is the target quantity.
C++
#include <iostream>
using namespace std;
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
void solveMathematical(int a, int b, int target) {
int gcd_val = gcd(a, b);
if (target % gcd_val != 0) {
cout << "No solution exists!" << endl;
return;
}
int x = 0, y = 0;
int steps = 0;
while (x != target && y != target) {
if (x == 0) {
x = a;
cout << "Fill jug 1" << endl;
} else if (y == b) {
y = 0;
cout << "Empty jug 2" << endl;
} else {
int pour = min(x, b - y);
x -= pour;
y += pour;
cout << "Pour " << pour << " liters from jug 1 to jug 2" << endl;
}
steps++;
}
cout << "Solution found in " << steps << " steps" << endl;
}
int main() {
int a = 3, b = 5, target = 4;
solveMathematical(a, b, target);
return 0;
}
You can also try this code with Online C++ Compiler
Java
#include <iostream>
using namespace std;
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
void solveMathematical(int a, int b, int target) {
int gcd_val = gcd(a, b);
if (target % gcd_val != 0) {
cout << "No solution exists!" << endl;
return;
}
int x = 0, y = 0;
int steps = 0;
while (x != target && y != target) {
if (x == 0) {
x = a;
cout << "Fill jug 1" << endl;
} else if (y == b) {
y = 0;
cout << "Empty jug 2" << endl;
} else {
int pour = min(x, b - y);
x -= pour;
y += pour;
cout << "Pour " << pour << " liters from jug 1 to jug 2" << endl;
}
steps++;
}
cout << "Solution found in " << steps << " steps" << endl;
}
int main() {
int a = 3, b = 5, target = 4;
solveMathematical(a, b, target);
return 0;
}
Java
public class WaterJugMathematical {
public static int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
public static void solveMathematical(int a, int b, int target) {
int gcdVal = gcd(a, b);
if (target % gcdVal != 0) {
System.out.println("No solution exists!");
return;
}
int x = 0, y = 0;
int steps = 0;
while (x != target && y != target) {
if (x == 0) {
x = a;
System.out.println("Fill jug 1");
} else if (y == b) {
y = 0;
System.out.println("Empty jug 2");
} else {
int pour = Math.min(x, b - y);
x -= pour;
y += pour;
System.out.println("Pour " + pour + " liters from jug 1 to jug 2");
}
steps++;
}
System.out.println("Solution found in " + steps + " steps");
}
public static void main(String[] args) {
int a = 3, b = 5, target = 4;
solveMathematical(a, b, target);
}
}
You can also try this code with Online Java Compiler
Python
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)
def solve_mathematical(a, b, target):
gcd_val = gcd(a, b)
if target % gcd_val != 0:
print("No solution exists!")
return
x, y = 0, 0
steps = 0
while x != target and y != target:
if x == 0:
x = a
print("Fill jug 1")
elif y == b:
y = 0
print("Empty jug 2")
else:
pour = min(x, b - y)
x -= pour
y += pour
print(f"Pour {pour} liters from jug 1 to jug 2")
steps += 1
print(f"Solution found in {steps} steps")
if __name__ == "__main__":
a = 3
b = 5
target = 4
solve_mathematical(a, b, target)
You can also try this code with Online Python Compiler
Output
Fill jug 1
Pour 3 liters from jug 1 to jug 2
Fill jug 1
Pour 2 liters from jug 1 to jug 2
Empty jug 2
Pour 1 liters from jug 1 to jug 2
Fill jug 1
Pour 3 liters from jug 1 to jug 2
Solution found in 8 steps
Bézout's identity Approach
Another effective method to solve the water jug problem is through Bézout's identity, a concept from number theory. Bézout's identity states that for any two integers a and b, there exist integers x and y such that:
ax+by=gcd(a,b)
Here, gcd(a,b) represents the greatest common divisor of aaa and bbb. This approach helps determine if it’s possible to measure a specific amount of water using jugs with given capacities.
For the water jug problem, if the desired amount of water is divisible by the greatest common divisor of the jug capacities, then it is possible to measure that exact amount. The key is to use the extended Euclidean algorithm to find the coefficients x and y, which tell you how much water to pour or transfer between jugs at each step.
By leveraging Bézout's identity and the extended Euclidean algorithm, you can efficiently calculate the steps needed to measure the desired quantity of water using two jugs.
# Function to calculate the Greatest Common Divisor (GCD) of two numbers
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
# Function to check if it's possible to measure the target amount of water
def can_measure_water(jug1_cap, jug2_cap, target):
# If the target is larger than the total capacity of both jugs
if target > jug1_cap + jug2_cap:
return False
# If either jug has zero capacity, check if target is 0 or sum of both capacities
if jug1_cap == 0 or jug2_cap == 0:
return target == 0 or target == jug1_cap + jug2_cap
# Return True if the target is divisible by the GCD of the jug capacities
return target % gcd(jug1_cap, jug2_cap) == 0
# Function to determine the steps to measure the desired amount of water
def measure_water(jug1_cap, jug2_cap, target):
if not can_measure_water(jug1_cap, jug2_cap, target):
return [] # Return an empty list if measurement is not possible
gcd_val = gcd(jug1_cap, jug2_cap)
a, b = jug1_cap // gcd_val, jug2_cap // gcd_val
# Ensure jug1 is the smaller jug
if a > b:
a, b = b, a
jug1_cap, jug2_cap = jug2_cap, jug1_cap
# Calculate how many times we need to pour the water
q2 = target // gcd_val
steps = []
while q2 > 0:
q1 = (target - b * q2) // a
# Append the steps for filling and pouring
steps.append(('fill', 1))
steps.append(('pour', 1, 2))
steps.append(('empty', 2))
steps.append(('pour', 1, 2))
steps.append(('fill', 1))
steps.append(('pour', 1, 2))
q2 -= 1
target -= a
return steps
# Example parameters
jug1_cap = 4
jug2_cap = 3
target = 2
# Call the function and print the steps if possible
if can_measure_water(jug1_cap, jug2_cap, target):
print(list(measure_water(jug1_cap, jug2_cap, target)))
else:
print("Cannot measure the desired amount of water.")
You can also try this code with Online Python Compiler
Output
[('fill', 1), ('pour', 1, 2), ('empty', 2), ('pour', 1, 2), ('fill', 1), ('pour', 1, 2), ('fill', 1), ('pour', 1, 2), ('empty', 2), ('pour', 1, 2), ('fill', 1), ('pour', 1, 2)]
You can also try this code with Online Python Compiler
Frequently Asked Questions
What are the approaches to solve the Water Jug problem?
The two main approaches to solve the Water Jug problem are the Breadth-First Search (BFS) algorithm and the mathematical approach using the greatest common divisor (GCD).
How do I determine if a solution exists for the Water Jug problem?
In the mathematical approach, if the target quantity is a multiple of the GCD of the jug capacities, then a solution exists. Otherwise, there is no solution.
Which search strategy is appropriate for the water jug problem?
The Breadth-First Search (BFS) strategy is commonly used for the water jug problem. BFS explores all possible states (amounts of water in the jugs) layer by layer, ensuring that the shortest solution path is found efficiently.
Conclusion
In this article, we talked about the Water Jug problem and discussed two approaches to solve it: the Breadth-First Search (BFS) algorithm and the mathematical approach which uses the greatest common divisor (GCD). We provided detailed explanations of each approach along with code implementations in C++, Java, and Python. The BFS approach guarantees finding the shortest path to the target quantity, while the mathematical approach provides a simple and efficient way to determine the solvability of the problem.
You can also practice coding questions commonly asked in interviews on Coding Ninjas Code360.
Also, check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry Experts.
19+ registered 
