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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Water and Jug Problem and Math problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →