LeetCode 0365. Water and Jug Problem Solution in Java, C++, Python & Go | Explanation + Code

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

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.

PythonJavaC++Go

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)(code-box)

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; } }(code-box)

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; } };(code-box)

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) }(code-box)