Water and Jug Problem

1. Handle the edge case: if x + y < target, it's impossible to measure the target amount. Return false.
2. Initialize a queue for BFS and add the starting state (0, 0).
3. Initialize a visited set to keep track of states we've already seen. Add (0, 0) to it. A pair (a, b) can be encoded as a * (y_capacity + 1) + b to be stored in a simple set of integers.
4. While the queue is not empty: a. Dequeue the current state, (curr_x, curr_y). b. If curr_x + curr_y == target, we have found a solution. Return true. c. Generate all possible next states from (curr_x, curr_y): - Fill jug 1: (x, curr_y) - Fill jug 2: (curr_x, y) - Empty jug 1: (0, curr_y) - Empty jug 2: (curr_x, 0) - Pour from jug 1 to jug 2: (curr_x - min(curr_x, y - curr_y), curr_y + min(curr_x, y - curr_y)) - Pour from jug 2 to jug 1: (curr_x + min(curr_y, x - curr_x), curr_y - min(curr_y, x - curr_x)) d. For each new state, if it has not been visited, add it to the queue and the visited set.
5. If the queue becomes empty and the target has not been reached, it's impossible. Return false.

We can think of the amounts of water in the two jugs as a state (a, b). The problem then becomes finding if a state where the sum of water equals target is reachable from the initial state (0, 0). BFS is a suitable algorithm for this because it explores the state space layer by layer, guaranteeing that we find the shortest sequence of operations if a solution exists (though we only need to know if it exists). We use a queue to store states to visit and a visited set to avoid processing the same state multiple times, which prevents infinite loops and redundant work.

1import java.util.HashSet;2import java.util.LinkedList;3import java.util.Queue;4import java.util.Set;5 6class Solution {7    public boolean canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {8        if (targetCapacity > jug1Capacity + jug2Capacity) {9            return false;10        }11 12        Queue<int[]> queue = new LinkedList<>();13        Set<Long> visited = new HashSet<>();14 15        int[] initialState = {0, 0};16        queue.offer(initialState);17        // Encode the state (x, y) as x * (jug2Capacity + 1) + y18        visited.add(0L);19 20        while (!queue.isEmpty()) {21            int[] current = queue.poll();22            int curr_x = current[0];23            int curr_y = current[1];24 25            if (curr_x + curr_y == targetCapacity) {26                return true;27            }28 29            // All possible next states30            int[][] nextStates = {31                // 1. Fill jug132                {jug1Capacity, curr_y},33                // 2. Fill jug234                {curr_x, jug2Capacity},35                // 3. Empty jug136                {0, curr_y},37                // 4. Empty jug238                {curr_x, 0},39                // 5. Pour from jug1 to jug240                {curr_x - Math.min(curr_x, jug2Capacity - curr_y), curr_y + Math.min(curr_x, jug2Capacity - curr_y)},41                // 6. Pour from jug2 to jug142                {curr_x + Math.min(curr_y, jug1Capacity - curr_x), curr_y - Math.min(curr_y, jug1Capacity - curr_x)}43            };44 45            for (int[] state : nextStates) {46                long stateCode = (long)state[0] * (jug2Capacity + 1) + state[1];47                if (!visited.contains(stateCode)) {48                    visited.add(stateCode);49                    queue.offer(state);50                }51            }52        }53 54        return false;55    }56}

1. Handle the trivial case: if x + y < target, it's impossible. Return false.
2. Handle the case where one of the jugs is 0. If x or y is 0, we can only measure target if target is 0 or equal to the non-zero capacity. This is implicitly handled by the GCD logic if we define gcd(a, 0) = a.
3. Calculate the greatest common divisor of x and y, let's call it g.
4. Check if target is divisible by g. If target % g == 0, return true. Otherwise, return false.

The problem can be reduced to a mathematical equation. Any amount of water that can be measured is a linear combination of the jug capacities, x and y. This means any achievable amount z can be expressed as z = m*x + n*y, where m and n are integers representing the number of times each jug is filled (positive m, n) or emptied (negative m, n).

Bézout's identity from number theory states that the equation m*x + n*y = z has integer solutions for m and n if and only if z is divisible by the greatest common divisor (GCD) of x and y.

Therefore, we only need to check two conditions:

1. The total amount of water cannot exceed the combined capacity of the jugs: target <= x + y.
2. The target amount must be a multiple of gcd(x, y).

If both conditions are met, the target is reachable. The GCD can be calculated efficiently using the Euclidean algorithm.

1class Solution {2    public boolean canMeasureWater(int x, int y, int target) {3        // The total amount of water can't exceed the sum of capacities.4        if (x + y < target) {5            return false;6        }7        8        // If target is 0, it's always possible (empty jugs).9        if (target == 0) {10            return true;11        }12 13        // According to Bézout's identity, the amount of water that can be measured14        // is a linear combination of x and y: z = m*x + n*y.15        // This equation has integer solutions for m and n if and only if16        // z is a multiple of gcd(x, y).17        int commonDivisor = gcd(x, y);18        19        return target % commonDivisor == 0;20    }21 22    // Helper function to compute GCD using iterative Euclidean algorithm23    private int gcd(int a, int b) {24        while (b != 0) {25            int temp = b;26            b = a % b;27            a = temp;28        }29        return a;30    }31}