İçeriğe geç

XOR numaraları

Ders 2 / 5 · 4 dk

XOR numaraları

Adım 1/7

XOR bütün listeyi tek bir değişkende biriktirir. Sıfırdan başla; ilk değer 4.

Fikir

XOR'un bütün işi gören iki özelliği var: x ^ x 0'dır, x ^ 0 da x. Üstelik sıraya da bakmaz.

O yüzden bütün listeyi baştan sona XOR'la; iki kez geçen her değer kendini siler. Geriye kalan değer tek sayıda geçmiştir — O(n) sürede ve O(1) bellekle.

Gerçek hayattan örnek

RAID 5, diğer disklerin XOR'u olan bir parity (eşlik) diski tutar. Herhangi tek bir diski kaybedersen, kalan her şeyi XOR'layarak onun içeriğini yeniden kurarsın: eksik blok, artık eşi olmayan değerdir.

Kod

Sıra sende

Boşluğu doldur.

def single_number(nums):
  acc = 0
  for x in nums:
      acc = acc ___ x
  return acc

print(single_number([9, 5, 9]))   # want 5

Mini quiz

1 / 3

`x ^ x` nedir?