# Water and Jug Problem
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/water-and-jug-problem)
Canonical: https://scaleengineer.com/dsa/problems/water-and-jug-problem
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Companies:** [Lyft](https://scaleengineer.com/companies/lyft), [Wells Fargo](https://scaleengineer.com/companies/wells-fargo)
---
## Problem
You are given two jugs with capacities `x` liters and `y` liters. You have an infinite water supply. Return whether the total amount of water in both jugs may reach `target` using the following operations:

* Fill either jug completely with water.
* Completely empty either jug.
* Pour water from one jug into another until the receiving jug is full, or the transferring jug is empty.

**Example 1:** 

**Input:**  x = 3, y = 5, target = 4 

**Output:**  true 

**Explanation:**

Follow these steps to reach a total of 4 liters:

1. Fill the 5-liter jug (0, 5).
2. Pour from the 5-liter jug into the 3-liter jug, leaving 2 liters (3, 2).
3. Empty the 3-liter jug (0, 2).
4. Transfer the 2 liters from the 5-liter jug to the 3-liter jug (2, 0).
5. Fill the 5-liter jug again (2, 5).
6. Pour from the 5-liter jug into the 3-liter jug until the 3-liter jug is full. This leaves 4 liters in the 5-liter jug (3, 4).
7. Empty the 3-liter jug. Now, you have exactly 4 liters in the 5-liter jug (0, 4).

Reference: The [Die Hard](https://www.youtube.com/watch?v=BVtQNK%5FZUJg&ab%5Fchannel=notnek01) example.

**Example 2:** 

**Input:**  x = 2, y = 6, target = 5 

**Output:**  false 

**Example 3:** 

**Input:**  x = 1, y = 2, target = 3 

**Output:**  true 

**Explanation:** Fill both jugs. The total amount of water in both jugs is equal to 3 now.

**Constraints:**

* `1 <= x, y, target <= 103`

# Approaches
## State-Space Search using Breadth-First Search (BFS)
This approach models the problem as a state-space graph. Each state is represented by the amount of water in the two jugs, `(jug1, jug2)`. We start from the initial state `(0, 0)` and explore all reachable states using Breadth-First Search (BFS). The goal is to find if any state `(a, b)` satisfies `a + b == target`.
**Time:** O(x * y), where `x` and `y` are the jug capacities. In the worst case, we might have to visit all possible states, and the number of states is `(x + 1) * (y + 1)`. · **Space:** O(x * y). The `visited` set and the queue can store up to `(x + 1) * (y + 1)` states in the worst case.
**Pros:** It's a very intuitive approach that directly simulates the process.; It will find a solution if one exists.; It can be adapted to find the minimum number of steps to reach the target.
**Cons:** It can be slow and memory-intensive for large jug capacities.; The number of states can be up to `(x + 1) * (y + 1)`, which can be large.
### Explanation
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.

```java
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

class Solution {
    public boolean canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
        if (targetCapacity > jug1Capacity + jug2Capacity) {
            return false;
        }

        Queue<int[]> queue = new LinkedList<>();
        Set<Long> visited = new HashSet<>();

        int[] initialState = {0, 0};
        queue.offer(initialState);
        // Encode the state (x, y) as x * (jug2Capacity + 1) + y
        visited.add(0L);

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int curr_x = current[0];
            int curr_y = current[1];

            if (curr_x + curr_y == targetCapacity) {
                return true;
            }

            // All possible next states
            int[][] nextStates = {
                // 1. Fill jug1
                {jug1Capacity, curr_y},
                // 2. Fill jug2
                {curr_x, jug2Capacity},
                // 3. Empty jug1
                {0, curr_y},
                // 4. Empty jug2
                {curr_x, 0},
                // 5. Pour from jug1 to jug2
                {curr_x - Math.min(curr_x, jug2Capacity - curr_y), curr_y + Math.min(curr_x, jug2Capacity - curr_y)},
                // 6. Pour from jug2 to jug1
                {curr_x + Math.min(curr_y, jug1Capacity - curr_x), curr_y - Math.min(curr_y, jug1Capacity - curr_x)}
            };

            for (int[] state : nextStates) {
                long stateCode = (long)state[0] * (jug2Capacity + 1) + state[1];
                if (!visited.contains(stateCode)) {
                    visited.add(stateCode);
                    queue.offer(state);
                }
            }
        }

        return false;
    }
}
```
### Algorithm
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`.

## Mathematical Approach using Bézout's Identity
This approach leverages a mathematical theorem known as Bézout's identity. It states that an amount `z` can be measured if and only if it's a multiple of the greatest common divisor (GCD) of the two jug capacities, `x` and `y`. Additionally, the target amount cannot exceed the total capacity of both jugs.
**Time:** O(log(min(x, y))). The dominant operation is the calculation of the GCD using the Euclidean algorithm. · **Space:** O(1). The algorithm uses a constant amount of extra space. If a recursive GCD is used, it would be O(log(min(x, y))) for the recursion stack.
**Pros:** Extremely efficient in both time and space.; Provides a solution with a simple and elegant mathematical insight.; Avoids complex state-space exploration.
**Cons:** The reasoning is less intuitive and requires knowledge of number theory (Bézout's identity).
### Explanation
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.

```java
class Solution {
    public boolean canMeasureWater(int x, int y, int target) {
        // The total amount of water can't exceed the sum of capacities.
        if (x + y < target) {
            return false;
        }
        
        // If target is 0, it's always possible (empty jugs).
        if (target == 0) {
            return true;
        }

        // According to Bézout's identity, the amount of water that can be measured
        // is a linear combination of x and y: z = m*x + n*y.
        // This equation has integer solutions for m and n if and only if
        // z is a multiple of gcd(x, y).
        int commonDivisor = gcd(x, y);
        
        return target % commonDivisor == 0;
    }

    // Helper function to compute GCD using iterative Euclidean algorithm
    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}
```
### Algorithm
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`.

# Solutions
### CSharp

```csharp
using System ; public class Solution { public bool CanMeasureWater ( int x , int y , int z ) { if ( x == 0 || y == 0 ) return z == x || z == y ; var gcd = GetGcd ( x , y ); return z >= 0 && z <= x + y && z % gcd == 0 ; } private int GetGcd ( int x , int y ) { while ( x > 0 ) { var quotient = x / y ; var reminder = x % y ; if ( reminder == 0 ) { return y ; } x = y ; y = reminder ; } throw new Exception ( "Invalid x or y" ); } }
```

### Java

```java
class Solution {
public
  boolean canMeasureWater(int jug1Capacity, int jug2Capacity,
                          int targetCapacity) {
    if (jug1Capacity + jug2Capacity < targetCapacity) {
      return false;
    }
    if (jug1Capacity == 0 || jug2Capacity == 0) {
      return targetCapacity == 0 ||
             jug1Capacity + jug2Capacity == targetCapacity;
    }
    return targetCapacity % gcd(jug1Capacity, jug2Capacity) == 0;
  }
private
  int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
}

```

### Python

```python
class Solution:
    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool: if jug1Capacity + jug2Capacity < targetCapacity: return False if jug1Capacity == 0 or jug2Capacity == 0: return targetCapacity == 0 or jug1Capacity + jug2Capacity == targetCapacity return targetCapacity % gcd(jug1Capacity, jug2Capacity) == 0

```

### CPP

```cpp
class Solution {
public:
  bool canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
    if (jug1Capacity + jug2Capacity < targetCapacity)
      return false;
    if (jug1Capacity == 0 || jug2Capacity == 0)
      return targetCapacity == 0 ||
             jug1Capacity + jug2Capacity == targetCapacity;
    return targetCapacity % gcd(jug1Capacity, jug2Capacity) == 0;
  }
  int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
};

```