Water and Jug Problem

Medium
1275.

Water and Jug Problem

Water and Jug Problem is a medium coding problem on math, depth-first search and breadth-first search, asked in Google and Microsoft interviews.

You have two empty jugs holding up to x and y litres, and an unlimited tap. The allowed operations are:

  • fill either jug to the brim;
  • empty either jug completely;
  • pour from one jug into the other until the receiving jug is full or the pouring jug is empty.

Return true if, after some sequence of operations, the total amount of water in the two jugs can be exactly target litres.

Example 1

Input
x = 3, y = 5, target = 4
Output
true
Explanation
Fill the 5, pour into the 3 (leaving 2), empty the 3, pour the 2 across, fill the 5, top the 3 up from it (leaving 4 in the 5-litre jug), then empty the 3: 4 litres in total.

Example 2

Input
x = 4, y = 6, target = 7
Output
false
Explanation
Every amount you can ever hold is even.

Example 3

Input
x = 1, y = 2, target = 3
Output
true

Constraints

  • 1 <= x, y, target <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} x
 * @param {number} y
 * @param {number} target
 * @return {boolean}
 */
var canMeasureWater = function(x, y, target) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Water and Jug Problem — Solution in Python, Java & C++

Water and Jug Problem solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Water and Jug Problem is a medium coding problem on math, depth-first search and breadth-first search, asked in Google and Microsoft interviews.

Problem statement

You have two empty jugs holding up to x and y litres, and an unlimited tap. The allowed operations are:

  • fill either jug to the brim;
  • empty either jug completely;
  • pour from one jug into the other until the receiving jug is full or the pouring jug is empty.

Return true if, after some sequence of operations, the total amount of water in the two jugs can be exactly target litres.

Example 1

Input: x = 3, y = 5, target = 4
Output: true
Explanation: Fill the 5, pour into the 3 (leaving 2), empty the 3, pour the 2 across, fill the 5, top the 3 up from it (leaving 4 in the 5-litre jug), then empty the 3: 4 litres in total.

Example 2

Input: x = 4, y = 6, target = 7
Output: false
Explanation: Every amount you can ever hold is even.

Example 3

Input: x = 1, y = 2, target = 3
Output: true

Constraints

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

Hints for Water and Jug Problem

  1. Hint 1

    Think of the total amount of water. Each operation changes the total by x, by y, or not at all.

  2. Hint 2

    So any total you can reach is a combination a*x + b*y — which totals of that form are actually reachable without exceeding the jugs?

  3. Hint 3

    By Bézout's identity, the reachable totals are exactly the multiples of gcd(x, y) that do not exceed x + y.

How to solve Water and Jug Problem

The reachable totals are exactly the multiples of gcd(x, y) between 0 and x + y.

Approach

  1. If target > x + y, the jugs cannot hold it: return false.
  2. Compute g = gcd(x, y) with the Euclidean algorithm.
  3. Return whether target is a multiple of g.

Why it works

Every operation either leaves the total unchanged (pouring) or adds or removes a full jug's worth (x or y), so every reachable total is an integer combination of x and y — a multiple of g. Conversely, repeatedly filling one jug and pouring it into the other, emptying the other whenever it is full, walks through the residues k*x mod y and produces every multiple of g up to y in one jug; adding a full second jug covers the rest up to x + y. That is Bézout's identity made concrete, and the BFS over all states agrees with it.

Complexity

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

Pitfalls

  • The target is the total in both jugs, not the content of one jug.
  • Forgetting the target <= x + y bound: 10 is a multiple of gcd(3, 5) but does not fit.
  • A full BFS over (x+1)(y+1) states works but costs a million states at the upper limit.

Reference solution

Python

def canMeasureWater(x: int, y: int, target: int) -> bool:
    if target > x + y:
        return False
    a, b = x, y
    while b:
        a, b = b, a % b
    return target % a == 0

Java

public static boolean canMeasureWater(int x, int y, int target) {
    if (target > x + y) return false;
    int a = x, b = y;
    while (b != 0) {
        int t = a % b;
        a = b;
        b = t;
    }
    return target % a == 0;
}

C++

bool canMeasureWater(int x, int y, int target) {
    if (target > x + y) return false;
    int a = x, b = y;
    while (b != 0) {
        int t = a % b;
        a = b;
        b = t;
    }
    return target % a == 0;
}

JavaScript

var canMeasureWater = function(x, y, target) {
    if (target > x + y) return false;
    var a = x, b = y;
    while (b !== 0) {
        var t = a % b;
        a = b;
        b = t;
    }
    return target % a === 0;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)