Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Mediummath-number-theory

Water and Jug Problem

Problem (yeniden ifade)

Kapasiteleri x ve y litre olan iki sürahın var. Doldur, boşalt veya birini diğerine dökebilirsin. İki sürahide toplam tam target litre olup olamayacağını döndür.

Sezgi

Her dökme toplamı ±x, ±y veya bir kombinasyon kadar değiştirir. Ölçülebilir miktarlar x + y’ye sığan gcd(x, y) katlarıdır. Bézout: ax + by = target tamsayıları vardır ancak gcd(x, y) target’ı bölerse.

Yaklaşımlar

Bézout özdeşliği

Doğrulanmadı

Zaman O(log min(x, y))Alan O(1)

Fikir. target == 0 → true. x + y < target → false. Değilse target % gcd(x, y) == 0. x + y < target koruması x = y = 0 ve pozitif target’ı da kapsar, gcd(0, 0)’a bölünmez.

Yürüyüş. 3 ve 5, target 4: gcd=1 4’ü böler, 8 ≥ 4 → true (klasik 5’likte 4). 2 ve 6, target 5: gcd=2 5’i bölmez → false.

Trade-off. Sürahi durumlarında BFS de çalışır ve daha “simülasyon,” ama yavaştır ve sayı teorisi noktasını kaçırır. Mülakat cevabı bu.

Çözüm

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;
}

Şablon bağlantısı

Math & Number Theory’nin GCD şekli: Euclid ulaşılabilirliği kararlaştırır. LC 1071 ile aynı gcd, string uzunlukları yerine kapasitelerde.

Yansıma

Hedef 0 ise true. x+y hedeften küçükse false. Değilse hedef gcd(x, y)’nin katı mı?
x = y = 0 ve hedef pozitif: toplam yetmez, gcd(0, 0)’a bölme.
Kapasite içindeki her kat elde edilir. BFS aynı cevabı verir, durum sayısı kapasitelerin çarpımıdır.