# LeetCode 365: Water and Jug Problem

## Problem Restatement

We are given two jugs with capacities `x` liters and `y` liters.

There is an infinite water supply.

We need to decide whether it is possible to measure exactly `target` liters using the two jugs.

At the end, the total amount of water in both jugs must be exactly `target`.

Allowed operations:

| Operation | Meaning |
|---|---|
| Fill | Fill either jug completely |
| Empty | Empty either jug completely |
| Pour | Pour from one jug into the other until the source is empty or the destination is full |

The problem asks whether the total amount of water in both jugs can reach `target` using these operations. Example: `x = 3`, `y = 5`, `target = 4` returns `true`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `x`, `y`, and `target` |
| Output | `True` if exactly `target` liters can be measured |
| Jug capacities | `x` and `y` liters |
| Final condition | Water in both jugs together equals `target` |
| Operations | Fill, empty, and pour |

Example function shape:

```python
def canMeasureWater(x: int, y: int, target: int) -> bool:
    ...
```

## Examples

Example 1:

```python
x = 3
y = 5
target = 4
```

This is possible.

One sequence is:

| Step | State |
|---|---|
| Start | `(0, 0)` |
| Fill 5-liter jug | `(0, 5)` |
| Pour 5 into 3 | `(3, 2)` |
| Empty 3-liter jug | `(0, 2)` |
| Pour 2 into 3 | `(2, 0)` |
| Fill 5-liter jug | `(2, 5)` |
| Pour 5 into 3 until 3 is full | `(3, 4)` |
| Empty 3-liter jug | `(0, 4)` |

Now the total water is `4`.

So the answer is:

```python
True
```

Example 2:

```python
x = 2
y = 6
target = 5
```

This is impossible.

Both jug sizes are even, so every measurable amount is even.

The target `5` is odd.

So the answer is:

```python
False
```

Example 3:

```python
x = 1
y = 2
target = 3
```

Fill both jugs.

The total is:

```python
1 + 2 = 3
```

So the answer is:

```python
True
```

## First Thought: Search All States

A direct solution is to model each state as:

```python
(a, b)
```

where:

| Variable | Meaning |
|---|---|
| `a` | Current water in jug `x` |
| `b` | Current water in jug `y` |

From each state, we can try all operations:

1. Fill jug `x`.
2. Fill jug `y`.
3. Empty jug `x`.
4. Empty jug `y`.
5. Pour `x` into `y`.
6. Pour `y` into `x`.

Then use BFS or DFS.

This works because capacities are bounded.

But the problem has a simpler mathematical solution.

## Key Insight

The measurable amounts are exactly the multiples of:

```python
gcd(x, y)
```

within the total capacity limit.

This comes from Bézout's identity.

For two integers `x` and `y`, all integer combinations:

```python
a * x + b * y
```

are multiples of `gcd(x, y)`.

The fill and empty operations effectively add or remove whole jug capacities. Pouring transfers water between jugs without changing the total amount. Together, these operations can measure exactly the amounts that are multiples of the greatest common divisor.

So `target` is measurable if and only if:

```python
target <= x + y
```

and:

```python
target % gcd(x, y) == 0
```

The first condition matters because the two jugs together cannot hold more than `x + y` liters at one time.

## Algorithm

1. If `target > x + y`, return `False`.
2. Compute:

```python
g = gcd(x, y)
```

3. Return whether:

```python
target % g == 0
```

For the official constraints, `x`, `y`, and `target` are positive, so no special zero-capacity handling is needed in the standard version. The statement uses capacities and target at least `1`.

## Correctness

The total water held by both jugs can never exceed `x + y`, because those are the two jug capacities. Therefore, if `target > x + y`, the answer must be `False`.

Every amount produced by fill and empty operations changes the total water by whole multiples of `x` or `y`. Pouring only moves water between jugs and does not change the total. Therefore, every reachable target amount must be an integer combination of `x` and `y`.

By Bézout's identity, an integer combination of `x` and `y` can equal `target` exactly when `target` is divisible by `gcd(x, y)`.

If `target` is divisible by `gcd(x, y)` and `target <= x + y`, the classical water jug construction can measure that amount using fill, empty, and pour operations.

Therefore, the algorithm returns `True` exactly for measurable targets.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(log min(x, y))` | Euclidean algorithm for GCD |
| Space | `O(1)` | Only a few integer variables |

## Implementation

```python
from math import gcd

class Solution:
    def canMeasureWater(self, x: int, y: int, target: int) -> bool:
        if target > x + y:
            return False

        return target % gcd(x, y) == 0
```

## Code Explanation

First check capacity:

```python
if target > x + y:
    return False
```

Even if the target is mathematically reachable as a linear combination, the two jugs cannot hold more than `x + y` liters at the same time.

Then compute the GCD:

```python
gcd(x, y)
```

The target is measurable only when it is divisible by that GCD:

```python
target % gcd(x, y) == 0
```

For example:

```python
x = 2
y = 6
target = 5
```

The GCD is:

```python
2
```

Since:

```python
5 % 2 != 0
```

the answer is `False`.

## Alternative Implementation: BFS

The BFS version is useful for understanding the operations directly.

```python
from collections import deque

class Solution:
    def canMeasureWater(self, x: int, y: int, target: int) -> bool:
        if target > x + y:
            return False

        queue = deque([(0, 0)])
        seen = {(0, 0)}

        while queue:
            a, b = queue.popleft()

            if a + b == target:
                return True

            states = []

            states.append((x, b))
            states.append((a, y))
            states.append((0, b))
            states.append((a, 0))

            pour = min(a, y - b)
            states.append((a - pour, b + pour))

            pour = min(b, x - a)
            states.append((a + pour, b - pour))

            for state in states:
                if state not in seen:
                    seen.add(state)
                    queue.append(state)

        return False
```

This version explores reachable jug states.

Its time and space are:

```python
O(x * y)
```

because there are at most `(x + 1) * (y + 1)` states.

The GCD solution is preferred.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.canMeasureWater(3, 5, 4) is True
    assert s.canMeasureWater(2, 6, 5) is False
    assert s.canMeasureWater(1, 2, 3) is True
    assert s.canMeasureWater(6, 10, 8) is True
    assert s.canMeasureWater(6, 10, 7) is False
    assert s.canMeasureWater(4, 9, 13) is True
    assert s.canMeasureWater(4, 9, 14) is False

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `(3, 5, 4)` | Classic reachable case |
| `(2, 6, 5)` | Target not divisible by GCD |
| `(1, 2, 3)` | Target equals total capacity |
| `(6, 10, 8)` | Reachable multiple of GCD |
| `(6, 10, 7)` | Not divisible by GCD |
| `(4, 9, 13)` | Fill both jugs |
| `(4, 9, 14)` | Larger than total capacity |