Solving the Two Water Jug Problem in Java

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:

Fill a jug completely
Empty a jug
Pour water from one jug to another until one jug is full or empty

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:

Fill a jug
Pour from one jug to another
Empty a jug if full
Repeat until d liters is obtained

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

Compile and run:

javac Solution.java
java Main

Output

6
-1

6 → Minimum steps to measure 4 liters with 3- and 5-liter jugs
-1 → Impossible to measure 46 liters with 8- and 56-liter jugs

Complexity Analysis

Time Complexity: O(m + n) → Each pouring step is bounded by jug capacities
Space Complexity: O(1) → No extra data structures are used

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.