Domain 2MediumCORE

Water and Jug Problem

We are given two jugs with fixed capacities, jug1Capacity and jug2Capacity, plus an infinite water source. We need to determine if we can measure exactly targetCapacity.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Math

365. Water and Jug Problem

Model: qwen3.5:9b
Topics: Math
FAANG asked: 1
Acceptance rate: 31.3%


Problem Breakdown

We are given two jugs with fixed capacities, jug1Capacity and jug2Capacity, plus an infinite water source. We need to determine if we can measure exactly targetCapacity.

Key Inputs:

  • Two integers representing jug sizes (AA, BB).
  • One integer for the target volume (CC).

Implicit Constraints & Edge Cases:

  1. Physical Limitation: You cannot hold more water than the sum of both jugs at any single moment to count as “measured”. Thus, if target > A + B, it is impossible regardless of GCD logic.
  2. Divisibility Logic: Every operation (filling or emptying) changes the total volume by multiples of AA and BB. This implies that any reachable measurable amount must be a linear combination (x⋅A+y⋅B=Cx \cdot A + y \cdot B = C). By number theory, this is only possible if C is divisible by gcd(A,B)\text{gcd}(A, B).
  3. Zero/One Capacities: Constraints state capacities are at least 1, so we don’t need to handle division by zero for GCD or empty jugs as inputs (though logic handles them naturally).

Intuition

Initially, a candidate might consider simulating the process using Breadth-First Search (BFS) on states (x,y)(x, y) where 0≤x≤A0 \le x \le A and 0≤y≤B0 \le y \le B. Why this fails: The state space size is roughly proportional to A×BA \times B. Given constraints up to 10610^6, a grid of that magnitude leads to Time Limit Exceeded (TLE) or Memory Limit Exceeded (MLE). We cannot iterate through every possible water level.

We need an O(1) mathematical solution. Key Insight: Think about the net change in volume relative to zero. Every time we fill Jug 1, we add AA. Every time we empty it, we subtract AA (conceptually). The same applies to Jug 2 (BB). Therefore, any reachable amount is of the form k1⋅A+k2⋅B=Ck_1 \cdot A + k_2 \cdot B = C, where k1,k2k_1, k_2 are integers. According to Bezout’s Identity, such an integer solution exists if and only if gcd(A,B)\text{gcd}(A, B) divides CC. We must also respect the physical constraint that we cannot measure more than what fits in both jugs combined (C≤A+BC \le A + B).

Approach

  1. Check the trivial upper bound: If targetCapacity exceeds the sum of both jug capacities (jug1Capacity + jug2Capacity), return False. We physically can’t hold that much water at once to measure it as a single unit in our buckets.
  2. Compute the Greatest Common Divisor (GCD) of the two jug capacities using Python’s built-in math.gcd.
  3. Check divisibility: If targetCapacity % gcd == 0, return True; otherwise, return False.

This approach leverages number theory to bypass state-space simulation entirely.

Complexity Analysis

  • Time: O(log⁡(min⁡(A,B)))O(\log(\min(A, B))). Computing the GCD takes logarithmic time relative to the inputs (Euclidean algorithm). All other operations are constant time checks.
  • Space: O(1)O(1). We only store a few integer variables; no recursion stack or data structures grow with input size.

Solution

import math

def canMeasureWater(jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:
    # Physical constraint: Cannot measure more than total capacity of both jugs combined
    if targetCapacity > jug1Capacity + jug2Capacity:
        return False
    
    # Mathematical constraint: Target must be a multiple of the GCD of capacities
    g = math.gcd(jug1Capacity, jug2Capacity)
    
    return targetCapacity % g == 0

# Example usage matching problem description
print(canMeasureWater(3, 5, 4))   # True (Die Hard example: fill 5->pour to 3->left 2. Empty small. Pour 2 into small. Fill big again -> pour 1L to full small -> leaves 4 in big)
print(canMeasureWater(2, 6, 5))   # False

Edge Cases Handled

  • Target > Sum of Capacities: Explicitly checked at the start (targetCapacity > jug1Capacity + jug2Capacity). Returns False immediately.
  • GCD Divisibility Failure: If target is not a multiple of GCD (e.g., capacities 3 and 5, target 4 works because gcd(3,5)=1 divides 4; but if capacity was 6 and 9 with target 7), the modulo check handles this.
  • Target = Capacity: Works naturally since capacity % gcd(capacity, other) == 0 is always true (gcd divides itself).