Show problems as
Classic problem #365MediumMathDepth-First SearchBreadth-First SearchBézout's LemmaEuclidean AlgorithmGreatest Common DivisorExtended Euclidean Algorithm

Water and Jug Problem

Real-world version: Measuring Out an Exact Amount With Two Cans
Tracked in this browser only
Read Water and Jug Problem on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Two cans hold x and y litres when full. There is an unlimited supply of water and a drain.

At any moment you may fill a can to the brim, empty a can out, or pour one can into the other until either the pouring can runs dry or the receiving can is full.

Return true when the two cans can be made to hold target litres between them.

Examples

Example 1

Input
x = 14, y = 21, target = 7
Output
true

The two sizes share the divisor 7, and 7 divides evenly by it and fits inside 35, so it can be measured out.

Example 2

Input
x = 2, y = 6, target = 5
Output
false

Both cans hold an even number of litres, so the total is always even and an odd target is out of reach.

Example 3

Input
x = 4, y = 6, target = 10
Output
true

The target is exactly both cans full, which is allowed, and it divides evenly by their shared divisor of 2.

Constraints

  • 1 <= x <= 1000
  • 1 <= y <= 1000
  • 1 <= target <= 1000

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def can_measure_water(x: int, y: int, target: int) -> bool:
Java
public boolean canMeasureWater(int x, int y, int target)

More on the same topics