Is Water and Jug Problem easy or hard?

Water and Jug Problem is generally classified as Medium difficulty. The brute-force state search using BFS is straightforward, but recognizing the mathematical GCD shortcut requires familiarity with number theory concepts.

Water and Jug Problem Python/Java solution

Most implementations either compute gcd(x, y) directly for the optimal solution or simulate jug operations using BFS. Both Python and Java versions typically include a gcd helper function or a queue-based traversal for the state graph.

How to solve Water and Jug Problem in O(log n)?

Use the number theory property derived from Bézout’s identity. First check if target <= x + y. Then compute gcd(x, y). If target is divisible by that gcd, the exact amount can be measured. The gcd computation via the Euclidean algorithm runs in O(log n).

What is the best approach for Water and Jug Problem?

The optimal approach uses the mathematical GCD insight. If target is greater than the combined capacity x + y, measuring it is impossible. Otherwise compute gcd(x, y) and check whether target % gcd(x, y) == 0. This solution runs in O(log(min(x, y))) time with O(1) space.

Is Water and Jug Problem asked at Google/Amazon/Meta?

Water and Jug Problem is a classic algorithm question that appears in interview preparation sets and coding platforms like LeetCode. Variants of the problem have been reported in interviews at companies such as Google and Amazon because it tests both graph search and mathematical reasoning.

What data structure is used in Water and Jug Problem?

The BFS approach uses a queue and a visited set to track explored jug states represented as pairs (a, b). Each state corresponds to a node in an implicit graph where edges represent valid operations like fill, empty, or pour.

What is the time complexity of Water and Jug Problem?

The optimal mathematical solution runs in O(log(min(x, y))) time because it relies on the Euclidean algorithm to compute the greatest common divisor. A BFS or DFS state search solution explores jug states and takes O(x * y) time and space.

Description Solution Video 10:32

365. Water and Jug Problem

Q: What is the best approach for Water and Jug Problem?

The optimal approach uses the mathematical GCD insight. If target is greater than the combined capacity x + y, measuring it is impossible. Otherwise compute gcd(x, y) and check whether target % gcd(x, y) == 0. This solution runs in O(log(min(x, y))) time with O(1) space.

Q: Is Water and Jug Problem asked at Google/Amazon/Meta?

Water and Jug Problem is a classic algorithm question that appears in interview preparation sets and coding platforms like LeetCode. Variants of the problem have been reported in interviews at companies such as Google and Amazon because it tests both graph search and mathematical reasoning.

Q: What data structure is used in Water and Jug Problem?

The BFS approach uses a queue and a visited set to track explored jug states represented as pairs (a, b). Each state corresponds to a node in an implicit graph where edges represent valid operations like fill, empty, or pour.

Q: What is the time complexity of Water and Jug Problem?

The optimal mathematical solution runs in O(log(min(x, y))) time because it relies on the Euclidean algorithm to compute the greatest common divisor. A BFS or DFS state search solution explores jug states and takes O(x * y) time and space.

Medium46.4% acceptance8 companies

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:

Fill the 5-liter jug (0, 5).
Pour from the 5-liter jug into the 3-liter jug, leaving 2 liters (3, 2).
Empty the 3-liter jug (0, 2).
Transfer the 2 liters from the 5-liter jug to the 3-liter jug (2, 0).
Fill the 5-liter jug again (2, 5).
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).
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 <= 10³

Asked at 8 companies

Tiktok Lyft Microsoft Uber

Google Oracle Apple Amazon

Topics

10:32

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def canMeasureWater(self, x: int, y: int, target: int) -> bool:
3        

Starter codePython 3Spaces: 4

Examples

Case 1

Input

3
5
4

Your code is saved on this device.Solution