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:
Example 1:
Input: x = 3, y = 5, target = 4
Output: true
Explanation:
Follow these steps to reach a total of 4 liters:
Reference: The Die Hard 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 <= 103Problem Overview: You are given two jugs with capacities x and y. Using fill, empty, and pour operations, determine whether it is possible to measure exactly target liters of water. The challenge is recognizing that the state space is small but the mathematical property behind the operations leads to a constant‑space optimal solution.
Approach 1: Breadth-First Search State Exploration (O(x * y) time, O(x * y) space)
Model each state as a pair (a, b) representing the current amount of water in jug1 and jug2. From any state you generate neighbors by applying the allowed operations: fill a jug, empty a jug, or pour from one jug to the other until one becomes empty or full. Run a BFS starting from (0,0) and track visited states to avoid cycles. If any state satisfies a == target, b == target, or a + b == target, the answer is true. BFS guarantees exploration of all reachable states and works well when demonstrating graph traversal using Breadth-First Search or Depth-First Search.
Approach 2: Mathematical Approach Using GCD (O(log(min(x, y))) time, O(1) space)
The jug operations follow a classic number theory result: any measurable volume must be a multiple of the greatest common divisor of the two jug capacities. If target > x + y, it is impossible because the combined capacity is insufficient. Otherwise compute gcd(x, y). If target % gcd(x, y) == 0, the target amount is measurable; otherwise it is not. This works because repeatedly pouring between jugs effectively generates linear combinations of x and y. The insight comes from Bézout’s identity, which is a standard technique in math-based algorithm problems.
Recommended for interviews: Start by describing the state-space search with BFS since it directly models the problem and proves correctness. Then present the mathematical optimization using GCD. Interviewers usually expect the GCD insight because it reduces the problem to O(log n) time and constant space, demonstrating strong problem‑solving and mathematical reasoning.
If you can reach a particular amount "target" of water using the two jug capacities x and y, it should be mathematically possible by considering the greatest common divisor (GCD) of x and y. This is based on the Diophantine equation which shows that target amount can be formed using a linear combination of jug capacities only if it is a multiple of the GCD. The condition to determine if we can measure exactly 'target' liters is if target <= x + y and target is a multiple of GCD(x, y).
The function gcd calculates the greatest common divisor of two numbers. The function canMeasureWater checks whether the target is reachable by ensuring the target is less than or equal to the sum of the jug capacities and is a multiple of the GCD of the jug capacities.
Time Complexity: O(log(min(x, y))) due to the GCD computation.
Space Complexity: O(1) as we only use a constant amount of additional space.
Breadth-First Search (BFS) can be used to simulate the water jug operations. We treat each state (a, b) of the jugs as a node, where a and b are the current water levels in the two jugs respectively. From each node, we can perform possible operations to reach new states, effectively exploring the state space until the target is found or all options are exhausted.
This C function uses a BFS algorithm with a queue to explore all possible water jug states until the target is found or all states are exhausted. A simple 2D array keeps track of visited states to avoid re-exploration.
Time Complexity: O(x * y) as each state is visited once.
Space Complexity: O(x * y) for storing visited states.
Let's denote jug1Capacity as x, jug2Capacity as y, and targetCapacity as z.
Next, we design a function dfs(i, j), which represents whether we can get z liters of water when there are i liters of water in jug1 and j liters of water in jug2.
The execution process of the function dfs(i, j) is as follows:
(i, j) has been visited, return false.i = z or j = z or i + j = z, return true.z liters of water by filling jug1 or jug2, or emptying jug1 or jug2, return true.z liters of water by pouring water from jug1 into jug2, or pouring water from jug2 into jug1, return true.The answer is dfs(0, 0).
The time complexity is O(x + y), and the space complexity is O(x + y). Here, x and y are the sizes of jug1Capacity and jug2Capacity respectively.
| Approach | Complexity |
|---|---|
| Mathematical Approach Using GCD | Time Complexity: O(log(min(x, y))) due to the GCD computation. |
| Breadth-First Search (BFS) Approach | Time Complexity: O(x * y) as each state is visited once. |
| DFS | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Breadth-First Search (State Exploration) | O(x * y) | O(x * y) | When modeling the problem as a graph of states or explaining jug operations step-by-step |
| Mathematical GCD Approach | O(log(min(x, y))) | O(1) | Optimal solution when recognizing the number theory property behind jug operations |
[BFS & Math] LeetCode 365. Water and Jug Problem English Version • happygirlzt • 11,837 views views
Watch 9 more video solutions →Practice Water and Jug Problem with our built-in code editor and test cases.
Practice on FleetCode