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

Missing Number

Problem (yeniden ifade)

[0, n] aralığında n adet benzersiz sayı. Eksik olanı bul.

Sezgi

0..n ile tüm nums’un XOR’u çiftleri iptal eder; kalan eksiktir.

Yaklaşımlar

0..n ile nums XOR

Doğrulanmadı

Zaman O(n)Alan O(1)

Fikir. x=0..n, nums ile katla.

Yürüyüş. [3,0,1] → 2.

Trade-off. Toplam formülü de O(n); XOR diğer dillerde taşma kaygısını önler.

Çözüm

export function missingNumber(nums: number[]): number {
  let x = nums.length;
  for (let i = 0; i < nums.length; i++) x ^= i ^ nums[i]!;
  return x;
}

export function missingNumber(nums: number[]): number {
  let x = nums.length;
  for (let i = 0; i < nums.length; i++) x ^= i ^ nums[i]!;
  return x;
}

Şablon bağlantısı

Bit XOR kimliği (single number ile aynı aile).

Yansıma

XOR 0..n ile dizideki her sayı. Çiftler düşer, eksik kalır. Toplam n(n+1)/2 - sum da aynı.
0 eksik olabilir. n eksik olabilir, dizi n sayıyı içermez. Tek eleman 0 ise eksik 1.
Toplam taşmasın. XOR taşmaz.