Skip to content

365. Water and Jug Problem

DifficultyMedium

Description

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:

  • Fill either jug completely with water.
  • Completely empty either jug.
  • Pour water from one jug into another until the receiving jug is full, or the transferring jug is empty.

 

Example 1:

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

Output: true

Explanation:

Follow these steps to reach a total of 4 liters:

  1. Fill the 5-liter jug (0, 5).
  2. Pour from the 5-liter jug into the 3-liter jug, leaving 2 liters (3, 2).
  3. Empty the 3-liter jug (0, 2).
  4. Transfer the 2 liters from the 5-liter jug to the 3-liter jug (2, 0).
  5. Fill the 5-liter jug again (2, 5).
  6. Pour from the 5-liter jug into the 3-liter jug until the 3-liter jug is full. This leaves 4 liters in the 5-liter jug (3, 4).
  7. Empty the 3-liter jug. Now, you have exactly 4 liters in the 5-liter jug (0, 4).

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 <= 103

Solutions

Solution 1: DFS

Thinking

Two jugs of capacities \(x,y\); can we measure \(z\)? Bézout’s identity says \(z\) must be a multiple of \(\gcd(x,y)\). A state search also decides it. There are \(O(xy)\) states.

\(\textit{dfs}(i,j)\) is the current pair. A seen state fails; a jug or their sum equal to \(z\) succeeds. Otherwise fill, empty, or pour. Start from \((0,0)\).

Let's denote \(\textit{jug1Capacity}\) as \(x\), \(\textit{jug2Capacity}\) as \(y\), and \(\textit{targetCapacity}\) as \(z\).

Next, we design a function \(\textit{dfs}(i, j)\), which represents whether we can get \(z\) liters of water when there are \(i\) liters of water in \(\textit{jug1}\) and \(j\) liters of water in \(\textit{jug2}\).

The execution process of the function \(\textit{dfs}(i, j)\) is as follows:

  • If \((i, j)\) has been visited, return \(\textit{false}\).
  • If \(i = z\) or \(j = z\) or \(i + j = z\), return \(\textit{true}\).
  • If we can get \(z\) liters of water by filling \(\textit{jug1}\) or \(\textit{jug2}\), or emptying \(\textit{jug1}\) or \(\textit{jug2}\), return \(\textit{true}\).
  • If we can get \(z\) liters of water by pouring water from \(\textit{jug1}\) into \(\textit{jug2}\), or pouring water from \(\textit{jug2}\) into \(\textit{jug1}\), return \(\textit{true}\).

The answer is \(\textit{dfs}(0, 0)\).

The time complexity is \(O(x + y)\), and the space complexity is \(O(x + y)\), where \(x\) and \(y\) are the sizes of \(\textit{jug1Capacity}\) and \(\textit{jug2Capacity}\) respectively.

 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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    private Set<Long> vis = new HashSet<>();
    private int x, y, z;

    public boolean canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
        x = jug1Capacity;
        y = jug2Capacity;
        z = targetCapacity;
        return dfs(0, 0);
    }

    private boolean dfs(int i, int j) {
        long st = f(i, j);
        if (!vis.add(st)) {
            return false;
        }
        if (i == z || j == z || i + j == z) {
            return true;
        }
        if (dfs(x, j) || dfs(i, y) || dfs(0, j) || dfs(i, 0)) {
            return true;
        }
        int a = Math.min(i, y - j);
        int b = Math.min(j, x - i);
        return dfs(i - a, j + a) || dfs(i + b, j - b);
    }

    private long f(int i, int j) {
        return i * 1000000L + j;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    bool canMeasureWater(int x, int y, int z) {
        using pii = pair<int, int>;
        stack<pii> stk;
        stk.emplace(0, 0);
        auto hash_function = [](const pii& o) { return hash<int>()(o.first) ^ hash<int>()(o.second); };
        unordered_set<pii, decltype(hash_function)> vis(0, hash_function);
        while (stk.size()) {
            auto st = stk.top();
            stk.pop();
            if (vis.count(st)) {
                continue;
            }
            vis.emplace(st);
            auto [i, j] = st;
            if (i == z || j == z || i + j == z) {
                return true;
            }
            stk.emplace(x, j);
            stk.emplace(i, y);
            stk.emplace(0, j);
            stk.emplace(i, 0);
            int a = min(i, y - j);
            int b = min(j, x - i);
            stk.emplace(i - a, j + a);
            stk.emplace(i + b, j - b);
        }
        return false;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
func canMeasureWater(x int, y int, z int) bool {
    type pair struct{ x, y int }
    vis := map[pair]bool{}
    var dfs func(int, int) bool
    dfs = func(i, j int) bool {
        st := pair{i, j}
        if vis[st] {
            return false
        }
        vis[st] = true
        if i == z || j == z || i+j == z {
            return true
        }
        if dfs(x, j) || dfs(i, y) || dfs(0, j) || dfs(i, 0) {
            return true
        }
        a := min(i, y-j)
        b := min(j, x-i)
        return dfs(i-a, j+a) || dfs(i+b, j-b)
    }
    return dfs(0, 0)
}

Comments