Water and Jug Problem

Problem Description

Given two jugs with capacities x and y liters and an unlimited water supply, determine if it is possible to measure exactly target liters. You can perform these operations:

• Fill either jug completely.
• Empty either jug completely.
• Pour water from one jug to the other until the receiving jug is full or the pouring jug is empty.

Key Insights

• The measurable water quantities are based on linear combinations of x and y.
• Mathematically, a target is achievable if and only if it is less than or equal to x + y and is a multiple of the greatest common divisor (gcd) of x and y.
• An alternative solution is graph search (BFS or DFS) where each state is (water in jug1, water in jug2), and you explore all valid operations to reach a state with the required water quantity.
• Using BFS/DFS requires tracking visited states to avoid cycles.

Space and Time Complexity

Time Complexity: O(x * y) in the worst-case scenario using BFS/DFS, as there can be at most (x+1) * (y+1) states.
Space Complexity: O(x * y) for the states visited.
For the mathematical solution:
Time Complexity: O(log(min(x, y))) (due to computing gcd)
Space Complexity: O(1)

Solution

We can solve the problem using a mathematical approach:

1. Check if target is 0 (always possible) or if target exceeds the total capacity (x + y), in which case it’s impossible.
2. Compute the gcd of x and y.
3. If target is a multiple of the gcd, then using Bézout's identity, it is possible to measure the amount; otherwise, it is not.

Alternatively, we can simulate all operations using BFS or DFS by representing each state as a pair (current amount in jug1, current amount in jug2). For each state, generate new states from all possible operations (fill, empty, pour) and check if the target measure is reached.

The following code solutions use the mathematical approach for efficiency and clarity.

Code Solutions