Skip to content

365. Water and Jug Problem

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.

\(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 \(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:

  • If \((i, j)\) has been visited, return \(false\).
  • If \(i = z\) or \(j = z\) or \(i + j = z\), return \(true\).
  • If we can get \(z\) liters of water by filling \(jug1\) or \(jug2\), or emptying \(jug1\) or \(jug2\), return \(true\).
  • If we can get \(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.

 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