The Two Water Jug problem is a classic puzzle in algorithm design. The challenge is: given two jugs with capacities m and n, measure exactly d liters of water using the following operations:
We want to find the minimum number of operations required to get exactly d liters in either jug, or determine if it's impossible.
Problem Example
Example 1
Input:
m = 3, n = 5, d = 4
Output:
6
Explanation: The steps are:
Fill 5-liter jug → (0, 5)
Pour from 5-liter to 3-liter jug → (3, 2)
Empty 3-liter jug → (0, 2)
Pour remaining 2 liters to 3-liter jug → (2, 0)
Fill 5-liter jug → (2, 5)
Pour 1 liter into 3-liter jug → (4, 3)
Result: 4 liters in 5-liter jug with 6 operations.
Example 2
Input:
m = 8, n = 56, d = 46
Output:
-1
Explanation: It's impossible to measure 46 liters with 8-liter and 56-liter jugs.
Approach
To solve this problem efficiently, we use mathematical reasoning:
Feasibility Check
A solution exists if and only if:
d is less than or equal to the maximum jug capacity, max(m, n)
d is a multiple of gcd(m, n) (greatest common divisor)
Formula:
if (d > Math.max(m, n) || d % gcd(m, n) != 0) return -1;
Two Strategies
Pour from m → n
Pour from n → m
The minimum number of operations is the smaller of the two approaches.
Operations Implementation
We simulate filling, emptying, and pouring between jugs until we reach d liters.
Java Implementation
class Solution {
// Function to return gcd of two numbers
private int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
// Function to simulate pouring operations
private int pour(int fromCap, int toCap, int d) {
int from = fromCap; // Fill from jug
int to = 0;
int step = 1;
while (from != d && to != d) {
int temp = Math.min(from, toCap - to); // Amount to pour
to += temp;
from -= temp;
step++;
if (from == d || to == d) break;
if (from == 0) { from = fromCap; step++; } // Refill from jug
if (to == toCap) { to = 0; step++; } // Empty to jug
}
return step;
}
public int minSteps(int m, int n, int d) {
if (d > Math.max(m, n)) return -1;
if (d % gcd(m, n) != 0) return -1;
// Return minimum operations from both strategies
return Math.min(pour(m, n, d), pour(n, m, d));
}
}
How the Code Works
Check Feasibility
The minSteps function first checks if measuring d liters is possible using the GCD condition.
Simulate Pouring
The pour function simulates step-by-step operations:
Calculate Minimum Steps
The solution returns the minimum steps between the two pouring strategies (m → n and n → m).
How to Execute
Save the code in a Java file, e.g., Solution.java
Create a main method to test:
public class Main {
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.minSteps(3, 5, 4)); // Output: 6
System.out.println(sol.minSteps(8, 56, 46)); // Output: -1
}
}
javac Solution.java
java Main
Output
6
-1
Complexity Analysis
Summary
The Two Water Jug problem can be solved efficiently using a combination of mathematical validation and simulation. By checking feasibility using the GCD condition and simulating two possible pouring strategies, we can determine the minimum number of steps required or conclude if the task is impossible.