Water and Jug Problem

Solvable iff target ≤ x + y and target is a multiple of gcd(x, y) — Bezout's identity.

Medium

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

May 16, 2026 3 min read

Problem#

Given two jugs of capacities x and y, can you measure exactly target liters using only fill, empty, and pour operations?

Examples#

x=3, y=5, target=4 → true.
x=2, y=6, target=5 → false.

Constraints#

1 <= x, y, target <= 10^6.

Approach#

By Bezout’s identity, integer combinations a*x + b*y produce exactly the multiples of gcd(x, y). We can measure target iff target <= x + y and target % gcd(x, y) == 0.

Solution#

class Solution {
public:
    bool canMeasureWater(int x, int y, int target) {
        if (target > x + y) return false;
        if (target == 0) return true;
        return target % __gcd(x, y) == 0;
    }
};

func canMeasureWater(x int, y int, target int) bool {
    if target > x+y {
        return false
    }
    if target == 0 {
        return true
    }
    gcd := func(a, b int) int {
        for b != 0 {
            a, b = b, a%b
        }
        return a
    }
    return target%gcd(x, y) == 0
}

import math

class Solution:
    def canMeasureWater(self, x: int, y: int, target: int) -> bool:
        if target > x + y:
            return False
        if target == 0:
            return True
        return target % math.gcd(x, y) == 0

function canMeasureWater(x, y, target) {
    if (target > x + y) return false;
    if (target === 0) return true;
    const gcd = (a, b) => {
        while (b !== 0) [a, b] = [b, a % b];
        return a;
    };
    return target % gcd(x, y) === 0;
}

class Solution {
    public boolean canMeasureWater(int x, int y, int target) {
        if (target > x + y) return false;
        if (target == 0) return true;
        return target % gcd(x, y) == 0;
    }

    private int gcd(int a, int b) {
        while (b != 0) {
            int t = a % b;
            a = b;
            b = t;
        }
        return a;
    }
}

function canMeasureWater(x: number, y: number, target: number): boolean {
    if (target > x + y) return false;
    if (target === 0) return true;
    const gcd = (a: number, b: number): number => {
        while (b !== 0) [a, b] = [b, a % b];
        return a;
    };
    return target % gcd(x, y) === 0;
}

Editorial#

gcd(x, y) is the finest granularity any combination of fills and pours can reach. As long as target fits in the total capacity and is a multiple of that granularity, a constructive sequence exists. The target == 0 corner case is trivially achievable.

Complexity#

Time: O(log min(x, y)) for gcd.
Space: O(1).

Water and Jug Problem

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#