Skip to main content

365. Water and Jug Problem

medium

Given two jugs of capacity x and y, determine whether you can measure exactly target liters using fill/empty/pour operations. Bezout's identity gives a one-line answer.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

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 the jugs can equal target liters using the following operations: Fill either jug completely with water; Empty either jug; Pour water from one jug into the other until the receiving jug is full, or the transferring jug is empty.

Constraints

  • 1 <= x, y, target <= 10^3

Examples

Example 1

Input
x = 3, y = 5, target = 4
Output
true

Explanation: Fill the 5-jug, pour 3 into the 3-jug, empty 3-jug, pour remaining 2 into 3-jug, fill 5-jug, pour 1 into 3-jug to top it off, leaving 4 in 5-jug.

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.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Operations let you obtain any non-negative linear combination of x and y bounded by x + y.

Hint 2

By Bezout's identity, the set of integers expressible as a*x + b*y (a, b integers) is exactly the multiples of gcd(x, y).

Hint 3

So target is reachable iff (a) target <= x + y AND (b) gcd(x, y) divides target.

Hint 4

Edge case target == 0 is trivially reachable. Edge case target == x + y: fill both.

Solution approach

Reveal approach

Bezout's identity: the set of integers expressible as a*x + b*y for integer a, b is exactly the multiples of gcd(x, y). The reachable amounts are also bounded above by the combined capacity x + y. So: return target == 0 OR (target <= x + y AND target % gcd(x, y) == 0). Use Euclid's algorithm for gcd. O(log min(x, y)) time, O(1) space. Edge cases handled by the formula: target == 0 (both jugs empty, trivially measurable), target == x or target == y or target == x + y (special-cased by the divisibility check). BFS alternative explores states (a, b) but is O(x * y) — works for the bounds here but is overkill.

Complexity

Time
O(log min(x, y))
Space
O(1)

Related patterns

  • math
  • number-theory
  • euclidean-algorithm

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Microsoft
  • Amazon

More Math practice problems

See all Math problems →