Dizideki Eksik Elemanı Bulma

İş görüşmelerinde sorulan klasik bir soru var; \([-1, 2, -1, 3, 2]\) gibi bir dizinin içinde, biri hariç tüm sayılardan 2 tane, diğer sayıdan ise 1 tane vardır. Bu sayı hangisidir?

Bu sorunun envai çeşit çözümü var. Her elemanın dizideki diğer çiftini arayabiliriz (\(O(n^2)\), hatta genelleştirilmiş durumda, k tekrar varsa \(O(n^k)\)), diziyi sıralayıp kontrol edebiliriz (\(O(nlogn)\)), hashtable'a atıp sayılarını tutabiliriz (\(O(n)\), fakat ekstradan alan gerekli) falan filan.

En yaygın çözümü de tüm elemanları xorlayıp çıkan sonucu dönmektir. Bu çözüm aşağıdaki iki kurala dayanır

\[a \oplus a = 0\]

\[a \oplus 0 = a\]

Bu durumda tüm 2 sayılar 0 olacak, tek sayıyı da 0'la xorlayıp sayının kendisini elde edeceğiz.

Peki bu problemi daha da genelleştirirsek nasıl çözebiliriz? Diyelim ki elimizdeki sayı dizisindeki sayılar, biri hariç \(n\) defa tekrar ediyor, diğer sayı da, \(0 < k < n\) olmak üzere, \(k\) defa tekrar ediyor olsun. \(k\) defa tekrar eden sayıyı nasıl bulabiliriz? Tabii ki yöntem olarak da \(O(1)\) ekstra alan kullanan ve \(O(n)\) işlemde biten bir yöntemi tercih ediyoruz.

İlk durumda sayıların 1 bitlik olduğunu düşünelim, yani dizi sadece 1 ve 0'lardan oluşuyor. Dizinin toplamını alırsak sonuç ya \(0 \times n + 1 \times k\) ya da \(1 \times n + 0 \times k\) olacak. Bu toplamların \(n\)'e göre modunu aldığımızda çıkan sonuç \(0\) ya da \(k\) olacak. Bu sonuclar da aslında

\[k \times a\]

ifadesine eşit. \(a\) da bizim aradığımız sayı.

Kısacası; ifadenin modu \(0\) ise aradığımız sayı \(0\), değilse \(1\).

32 bitlik sayı dizilerinde ise yapmamız gereken, bu işlemi tüm sayılardaki her bite uygulamak. sonrasında çıkan sonuçlar tek tek bize \(k\) defa tekrarlanan sayıyı verecek.

Genel çözümün kodu aşağıdaki gibi olacak.

Bu çözümde işaret bitini de dikkate aldığımız için bu çözüm negatif sayılar için de çalışacaktır.