LeetCode 365 - Water and Jug Problem

The problem gives us two water jugs with capacities x and y. We can perform only three types of operations: - Fill a jug completely - Empty a jug completely - Pour water from one jug into the other until either the source jug becomes empty or the destination jug becomes full…

leetcodemediummathdepth-first-searchbreadth-first-search

LeetCode Problem 365

Difficulty: 🟡 Medium
Topics: Math, Depth-First Search, Breadth-First Search

Solution

Problem Understanding

The problem gives us two water jugs with capacities x and y. We can perform only three types of operations:

  • Fill a jug completely
  • Empty a jug completely
  • Pour water from one jug into the other until either the source jug becomes empty or the destination jug becomes full

Our goal is to determine whether it is possible to measure exactly target liters using these operations.

The state of the system at any moment can be represented as (a, b), where a is the current amount of water in the first jug and b is the current amount in the second jug. The problem does not require that the water be contained in a specific jug. The only requirement is that the total amount of water available between the two jugs equals target.

For example, if x = 3, y = 5, and target = 4, then having states like (0,4) or (1,3) would both satisfy the requirement because the total water equals 4.

The constraints are relatively small:

  • 1 <= x, y, target <= 1000

These limits mean even graph traversal solutions such as BFS or DFS are feasible because the total number of states is bounded by (x + 1) * (y + 1). However, there is also a mathematical observation that leads to a much cleaner and more efficient solution.

Several edge cases are important to recognize immediately.

If target > x + y, the answer is automatically false because even when both jugs are completely full, there is not enough total capacity to hold the target amount.

If target == 0, the answer would trivially be true, although the constraints guarantee target is at least 1.

If one jug already equals the target, or if the combined capacity equals the target, the answer is immediately true.

The most important mathematical edge case is divisibility. Some targets are fundamentally impossible to construct because of number theory properties. For example, with jugs of size 2 and 6, every measurable quantity must be divisible by 2, so 5 can never be produced.

Approaches

Brute Force Approach

A straightforward solution is to model the problem as a graph traversal problem.

Each state is represented by (a, b), where:

  • a is the amount of water in jug x
  • b is the amount of water in jug y

From every state, we can generate up to six possible next states:

  • Fill jug x
  • Fill jug y
  • Empty jug x
  • Empty jug y
  • Pour from x into y
  • Pour from y into x

We can perform BFS or DFS starting from (0, 0) and explore all reachable states. If we ever encounter a state where:

a + b == target

then the answer is true.

This approach is correct because it exhaustively explores every reachable configuration of the two jugs. If a valid solution exists, traversal will eventually find it.

However, although the constraints are manageable, this approach is still more expensive than necessary. The state space can contain up to:

(x + 1) * (y + 1)

states, and each state generates multiple transitions.

Optimal Mathematical Approach

The key insight comes from Bézout's Identity from number theory.

For two integers x and y, any measurable amount must be a multiple of:

gcd(x, y)

This means a target is achievable if and only if:

  1. target <= x + y
  2. target % gcd(x, y) == 0

The reasoning is that every operation preserves the property that the amount of water in the system is a linear combination of x and y.

Bézout's Identity states that integers of the form:

ax + by

are exactly the multiples of gcd(x, y).

Therefore, if the target is divisible by the greatest common divisor of the jug sizes, then the target can be constructed through repeated pouring operations.

This transforms the problem from graph traversal into a simple mathematical check.

Approach Time Complexity Space Complexity Notes
Brute Force O(x * y) O(x * y) Explores all reachable jug states using BFS or DFS
Optimal O(log(min(x, y))) O(1) Uses Bézout's Identity and GCD

Algorithm Walkthrough

Optimal Algorithm

  1. First, check whether the target exceeds the total capacity of both jugs.

If:

target > x + y

then it is impossible to measure the target because the jugs together cannot hold enough water. 2. If the target exactly equals either jug capacity or the combined capacity, return true.

These are direct solutions that require no additional operations. 3. Compute the greatest common divisor of x and y.

The GCD represents the smallest measurable unit obtainable using repeated pouring operations. 4. Check whether the target is divisible by the GCD.

If:

target % gcd(x, y) == 0

then the target is achievable.

Otherwise, it is impossible. 5. Return the result of the divisibility check.

Why it works

The algorithm works because every measurable amount formed through filling, emptying, and pouring operations must be representable as an integer linear combination of the two jug sizes.

By Bézout's Identity:

$ax + by = \gcd(x,y)$

all measurable quantities are multiples of gcd(x, y). Therefore, a target can be measured exactly if and only if it is divisible by the GCD and does not exceed the total capacity of the jugs.

Python Solution

class Solution:
    def canMeasureWater(self, x: int, y: int, target: int) -> bool:
        if target > x + y:
            return False
        
        def gcd(a: int, b: int) -> int:
            while b:
                a, b = b, a % b
            return a
        
        return target % gcd(x, y) == 0

The implementation begins with the most important impossibility check. If the target exceeds the combined capacity of the two jugs, there is no valid sequence of operations that can produce the desired amount.

Next, the solution computes the greatest common divisor using the Euclidean algorithm. The Euclidean algorithm repeatedly replaces the pair (a, b) with (b, a % b) until b becomes zero. The remaining value of a is the GCD.

Finally, the algorithm checks whether the target is divisible by the GCD. If it is divisible, the target is measurable. Otherwise, it is impossible.

The solution is concise because the mathematical insight completely eliminates the need for state exploration.

Go Solution

func canMeasureWater(x int, y int, target int) bool {
    if target > x+y {
        return false
    }

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

func gcd(a int, b int) int {
    for b != 0 {
        a, b = b, a%b
    }
    return a
}

The Go implementation follows the same mathematical approach as the Python version. The main difference is that helper functions must be declared separately in Go.

Go integers are sufficient for the given constraints, so there is no risk of overflow. The iterative Euclidean algorithm is efficient and avoids recursion overhead.

Worked Examples

Example 1

Input:

x = 3
y = 5
target = 4

First, check total capacity:

Value Result
x + y 8
target 4

Since 4 <= 8, continue.

Now compute the GCD:

Step a b
Initial 3 5
Iteration 1 5 3
Iteration 2 3 2
Iteration 3 2 1
Iteration 4 1 0

So:

gcd(3, 5) = 1

Now check divisibility:

Expression Result
4 % 1 0

Since the remainder is 0, the answer is true.

Example 2

Input:

x = 2
y = 6
target = 5

Check capacity:

Value Result
x + y 8
target 5

Continue because 5 <= 8.

Compute GCD:

Step a b
Initial 2 6
Iteration 1 6 2
Iteration 2 2 0

So:

gcd(2, 6) = 2

Check divisibility:

Expression Result
5 % 2 1

The remainder is not zero, so the answer is false.

Example 3

Input:

x = 1
y = 2
target = 3

Check capacity:

Value Result
x + y 3
target 3

Since the target equals the combined capacity, it is immediately achievable.

Answer: true.

Complexity Analysis

Measure Complexity Explanation
Time O(log(min(x, y))) Euclidean algorithm for GCD computation
Space O(1) Only a few integer variables are used

The dominant operation is the Euclidean GCD algorithm. Each iteration reduces the problem size significantly, producing logarithmic time complexity. No additional data structures proportional to input size are required, so the space complexity remains constant.

Test Cases

solution = Solution()

assert solution.canMeasureWater(3, 5, 4) == True   # classic solvable example
assert solution.canMeasureWater(2, 6, 5) == False  # target not divisible by gcd
assert solution.canMeasureWater(1, 2, 3) == True   # target equals total capacity

assert solution.canMeasureWater(1, 1, 2) == True   # both jugs completely filled
assert solution.canMeasureWater(1, 1, 1) == True   # one jug already equals target
assert solution.canMeasureWater(6, 10, 8) == True  # divisible by gcd(6,10)=2
assert solution.canMeasureWater(6, 10, 7) == False # not divisible by gcd

assert solution.canMeasureWater(1000, 1000, 2000) == True  # maximum capacity
assert solution.canMeasureWater(1000, 999, 1) == True      # coprime jug sizes
assert solution.canMeasureWater(4, 6, 15) == False         # target exceeds capacity

assert solution.canMeasureWater(7, 14, 21) == True  # target equals total capacity
assert solution.canMeasureWater(7, 14, 5) == False  # impossible odd target
assert solution.canMeasureWater(8, 12, 4) == True   # gcd directly equals target
Test Why
(3, 5, 4) Standard solvable example
(2, 6, 5) Target not divisible by GCD
(1, 2, 3) Target equals combined capacity
(1, 1, 2) Both jugs fully used
(1, 1, 1) One jug already matches target
(6, 10, 8) Reachable through GCD divisibility
(6, 10, 7) Impossible due to divisibility
(1000, 1000, 2000) Upper boundary capacity case
(1000, 999, 1) Coprime capacities allow all values
(4, 6, 15) Target larger than total capacity
(7, 14, 21) Exact total capacity case
(7, 14, 5) Odd target impossible with even GCD
(8, 12, 4) Target equals GCD

Edge Cases

One important edge case occurs when the target exceeds the total capacity of the two jugs. For example, if x = 3, y = 5, and target = 10, there is simply not enough physical capacity to hold 10 liters. A naive implementation that only checks divisibility could incorrectly return true. The implementation prevents this bug by checking target > x + y before performing the GCD calculation.

Another important edge case occurs when the jug capacities share a nontrivial GCD. For example, with capacities 2 and 6, every measurable amount must be divisible by 2. A traversal solution might eventually discover this implicitly, but the mathematical solution detects it immediately. The implementation correctly handles this by requiring:

target % gcd(x, y) == 0

A third edge case occurs when the target equals the combined capacity of both jugs. For example, x = 1, y = 2, and target = 3. Some incorrect implementations only check whether the target equals one individual jug size, missing the possibility of filling both jugs completely. The current implementation handles this naturally because target <= x + y and the divisibility condition both hold.

Another subtle edge case involves coprime jug sizes such as 999 and 1000. Since their GCD is 1, every target from 1 to 1999 is measurable. This is an important correctness property because it demonstrates why the GCD condition is both necessary and sufficient.