#365

Medium

auto_awesomeMath plus Depth-First Search

LeetCode Problem Workspace

Water and Jug Problem

Determine if two jugs with given capacities can measure an exact target amount using math and DFS strategies efficiently.

math depth first search breadth first search

Problem Statement

You are given two jugs with capacities x liters and y liters and an unlimited water supply. Determine whether it is possible to measure exactly target liters using the following operations: fill any jug completely, empty any jug, or pour water from one jug to the other until either jug is full or empty.

Return true if it is possible to reach exactly target liters in either jug or their combined total. For example, if x = 3, y = 5, and target = 4, the answer is true by carefully pouring between jugs. If x = 2, y = 6, and target = 5, the answer is false since no sequence of operations can reach 5 liters.

Examples

Example 1

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

Output: true

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 details omitted.

Example 3

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

Output: true

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

Constraints

1 <= x, y, target <= 103

Solution Approach

Mathematical GCD Check

Use the greatest common divisor (GCD) of x and y to determine reachability. The target is achievable only if target % GCD(x, y) == 0 and target <= max(x, y). This eliminates unnecessary DFS explorations early.

Depth-First Search Simulation

Simulate all possible jug states recursively. Start with (0, 0) and at each step, either fill, empty, or pour between jugs. Track visited states to prevent cycles and stop immediately if target liters are found in any state.

Breadth-First Search Alternative

BFS ensures the shortest sequence of operations is considered first. Use a queue of jug states, applying all possible operations at each step and marking visited states. This prevents infinite loops and confirms target reachability efficiently.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time and space complexity depend on the approach: the DFS/BFS can explore up to O(x*y) unique jug states, while the GCD method runs in constant time O(log(min(x,y))). Using state pruning reduces unnecessary recursion and queue expansions.

What Interviewers Usually Probe

They may hint at mathematical properties like GCD to optimize the solution.
Expect questions on avoiding infinite loops when simulating jug operations.
They often check understanding of BFS vs DFS trade-offs in state exploration.

Common Pitfalls or Variants

Common pitfalls

Failing to check the GCD condition and running full DFS unnecessarily.
Not marking visited states, causing infinite recursion or repeated computations.
Assuming the target must be in a single jug instead of the total combined water.

Follow-up variants

Compute the minimum number of steps to reach the target liters using BFS.
Allow fractional jug capacities and target values to test floating-point handling.
Generalize to three or more jugs with arbitrary capacities and target liters.

FAQ

Can the Water and Jug Problem always be solved with DFS alone?

DFS can explore all states, but without the GCD check and visited state tracking, it may be inefficient or enter infinite loops.

Why is the GCD important in this problem?

The target volume must be a multiple of the GCD of x and y for it to be achievable; otherwise, no sequence of fills and pours can reach it.

Should I prefer BFS or DFS for this problem?

DFS is simpler for reachability checks, while BFS is preferable if the interviewer asks for minimal operation sequences.

Does the combined water from both jugs count toward the target?

Yes, the target can be reached in either jug individually or as the sum of both jugs.

What are common mistakes when implementing this pattern?

Ignoring the GCD shortcut, forgetting to track visited states, or assuming the target must be in a single jug rather than the total.

terminal

Solution

Solution 1: DFS

Let's denote $jug1Capacity$ as $x$, $jug2Capacity$ as $y$, and $targetCapacity$ as $z$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def canMeasureWater(self, x: int, y: int, z: int) -> bool:
        def dfs(i: int, j: int) -> bool:
            if (i, j) in vis:
                return False
            vis.add((i, j))
            if i == z or j == z or i + j == z:
                return True
            if dfs(x, j) or dfs(i, y) or dfs(0, j) or dfs(i, 0):
                return True
            a = min(i, y - j)
            b = min(j, x - i)
            return dfs(i - a, j + a) or dfs(i + b, j - b)

        vis = set()
        return dfs(0, 0)

Continue Practicing

#672 bulb switcher ii #399 evaluate division #329 longest increasing path in a matrix