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:

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

Example function shape:

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

Examples

Example 1:

x = 3
y = 5
target = 4

This is possible.

One sequence is:

Now the total water is 4.

So the answer is:

True

Example 2:

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:

False

Example 3:

x = 1
y = 2
target = 3

Fill both jugs.

The total is:

1 + 2 = 3

So the answer is:

True

First Thought: Search All States

A direct solution is to model each state as:

(a, b)

where:

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:

gcd(x, y)

within the total capacity limit.

This comes from Bézout’s identity.

For two integers x and y, all integer combinations:

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:

target <= x + y

and:

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:

g = gcd(x, y)

3. Return whether:

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

Implementation

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:

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:

gcd(x, y)

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

target % gcd(x, y) == 0

For example:

x = 2
y = 6
target = 5

The GCD is:

2

Since:

5 % 2 != 0

the answer is False.

Alternative Implementation: BFS

The BFS version is useful for understanding the operations directly.

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:

O(x * y)

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

The GCD solution is preferred.

Testing

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: