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 (, ).
- One integer for the target volume ().
Implicit Constraints & Edge Cases:
- 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. - Divisibility Logic: Every operation (filling or emptying) changes the total volume by multiples of and . This implies that any reachable measurable amount must be a linear combination (). By number theory, this is only possible if
Cis divisible by . - 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 where and . Why this fails: The state space size is roughly proportional to . Given constraints up to , 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 . Every time we empty it, we subtract (conceptually). The same applies to Jug 2 (). Therefore, any reachable amount is of the form , where are integers. According to Bezout’s Identity, such an integer solution exists if and only if divides . We must also respect the physical constraint that we cannot measure more than what fits in both jugs combined ().
Approach
- Check the trivial upper bound: If
targetCapacityexceeds the sum of both jug capacities (jug1Capacity + jug2Capacity), returnFalse. We physically can’t hold that much water at once to measure it as a single unit in our buckets. - Compute the Greatest Common Divisor (GCD) of the two jug capacities using Python’s built-in
math.gcd. - Check divisibility: If
targetCapacity % gcd == 0, returnTrue; otherwise, returnFalse.
This approach leverages number theory to bypass state-space simulation entirely.
Complexity Analysis
- Time: . Computing the GCD takes logarithmic time relative to the inputs (Euclidean algorithm). All other operations are constant time checks.
- Space: . 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). ReturnsFalseimmediately. - 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) == 0is always true (gcd divides itself).