Problem 39.3 · Math for Coding InterviewsMedium

Water and Jug Problem

PatternNumber Theory and Combinatorics Graph BFS

What it teaches: Bézout's identity: reachable amounts are multiples of gcd(x, y) up to x + y.

Practise it on judges as “Water and Jug Problem”.

In plain words

You have a 3-litre jug and a 5-litre jug and a tap. By filling, emptying and pouring, the amounts you can ever have are exactly the multiples of the greatest common divisor of the two sizes, as long as it fits in both jugs together. So you just check two things.

Return true if target litres can be measured. Example: x = 3, y = 5, target = 4 → true.

The problem

With jugs of x and y litres (fill, empty, pour), can you measure exactly target litres in total?

Example 1

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

Constraints

1 ≤ x, y, target ≤ 10³

Pattern clues in the wording

→ Combinations of two step sizes

These clues point to Number Theory and Combinatorics: GCD, primes, modular arithmetic, fast power and counting formulas that turn loops into a few lines of math.

Stuck? Take one hint at a time

Solution · starter

class Solution {
    public boolean canMeasureWater(int x, int y, int target) {
        return false;
    }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#	Input	Expected
1	x = 3 y = 5 target = 4	true
2	x = 2 y = 6 target = 5	false
3	x = 1 y = 2 target = 3	true

From slow to fast

Approaches

1. GCD test · O(log min(x, y))

GCD test

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

target ≤ x + y and target % gcd(x, y) == 0.

▶ Dry run: Fits, and is a multiple of the GCDx = 3, y = 5, target = 4

fits?(vars)

x + y: 8target 4 ≤ 8: yes

Step 1/3Both jugs together hold 8 litres, so 4 litres can fit.

Approach 1

class Solution {
    public boolean canMeasureWater(int x, int y, int target) {
        return target <= x + y && target % gcd(x, y) == 0;
    }

    private int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
}

Verdict: BFS over (a, b) states also works but is O(x × y).

Before you submit

Edge cases and common mistakes

Test these inputs

target = x + y
target larger than both jugs

Mistakes people make

Forgetting the capacity limit x + y.

Interview

Follow-up questions

How would BFS model it?

Command Palette

The problem

Approaches

GCD test

Edge cases and common mistakes

Follow-up questions