Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediummath-number-theory

Water and Jug Problem

Problem (restated)

You have two jugs of capacities x and y liters. You may fill, empty, or pour one into the other. Return whether you can have exactly target liters in total in the two jugs.

Intuition

Every pour changes the total by ±x, ±y, or a combination. The measurable amounts are exactly the multiples of gcd(x, y) that fit in x + y. Bézout: there exist integers a, b with ax + by = target iff gcd(x, y) divides target.

Approaches

Bézout identity

Unverified

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

Idea. target == 0 → true. If x + y < target → false. Else target % gcd(x, y) == 0. The x + y < target guard also covers x = y = 0 with a positive target, so you never divide by gcd(0, 0).

Walkthrough. 3 and 5, target 4: gcd=1 divides 4, 8 ≥ 4 → true (classic 4 in the 5-jug). 2 and 6, target 5: gcd=2 does not divide 5 → false.

Trade-offs. BFS on jug states also works and is more “simulation,” but it is slower and misses the number-theory punchline. This is the interview answer.

Solution

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

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

Template connection

GCD shape of Math & Number Theory: Euclid decides reachability. Same gcd as LC 1071, applied to capacities instead of string lengths.

Reflection

Target 0 is true. If x + y < target, the answer is false. Otherwise the target must be a multiple of gcd(x, y).
x = y = 0 with a positive target fails the sum check, so you never call gcd(0, 0).
Every multiple that fits in the jugs is reachable. BFS of the jug states returns the same answer, with a state space the product of the capacities.