Arrayde tekrar etmeyen elemanı bulma

[Bowman]

Bu bir leetcode sorusu. Soru şu bir array var ve arrayin içerisinde tekrar etmeyen bir elemanı bulmalıyım. Atıyorum int nums[] = {0,-1,2,0,3,5,-1,3,5}; diye bir array olsun. Arrayda 2 hariç her elemandan bir tane daha var. Benim burada kendisinden bir tane daha olmayan elemanı bulmalıyım.

Adamlar xor kullanarak çözüme ulaşmışlar.

#include <stdio.h>

int singleNumber(int* nums, int numsSize)
{
    int result = 0;
    for (int i = 0; i < numsSize; i++)
    {
        result ^= nums[i];
    }
    return result;
}

int main(void)
{
    int nums[] = {0,-1,2,0,3,5,-1,3,5};
   
    printf("%d",singleNumber(nums,9));  
   
    return 0;
}

Şöyle bir çözüm üretilmiş ama ben nasıl çözdüklerini anlamadım. Adım adım gitmeye çalıştım kodda. XOR kapısı inputlar aynı olduğunda 0 farklı olduğunda 1 veriyor. Bir sayıyı 0 ile XOR yapmam halinde sayının kendisini elde ederim.

For içerisinde kodun döndüğünü varsayayım.
i = 0 -> result = result^nums[0] -> 0^0 = 0
i = 1 -> result = result ^nums[1]-> 0^-1 = -1
i = 2 -> result = result^nums[2] -> -1^2 = 1
i = 3 -> result = result^nums[3] -> 1 ^ 0 = 1 şeklinde gidiyor olarak değerlendirdim. Bu kodun çıktsı nasıl direkt 2 yi verebilir. Nerede hata yapıyorum.

 

[taydin]

Sorunun kriterlerinde, tekrar edilen sayıların TAM OLARAK 2 kere tekrar edildiğini belirtiyor. Bir sayı kendisi ile XOR edilirse ne çıkar?

 

[Bowman]

Sorunun kriterlerinde, tekrar edilen sayıların TAM OLARAK 2 kere tekrar edildiğini belirtiyor. Bir sayı kendisi ile XOR edilirse ne çıkar?

0 değil mi ? Çünkü 2 sayı da aynı.

 

[taydin]

Bu durumda tüm array elemanları XOR edilirse sonuç ne olur?

 

[Bowman]

Bu durumda tüm array elemanları XOR edilirse sonuç ne olur?

İşte benim aklım burada karıştı soruda yazdığım gibi adım adım sırayla xor ettim.

 

[taydin]

Tamam algoritmayı anladın ama adım adım yapınca aynı sonuca ulaşmıyorum diyorsun. Orada görülen adımlarda -1 XOR 2 = 1 demişsin. Bu doğru değil. Doğrusu -3 olacak.

 

[Bowman]

Tamam algoritmayı anladın ama adım adım yapınca aynı sonuca ulaşmıyorum diyorsun. Orada görülen adımlarda -1 XOR 2 = 1 demişsin. Bu doğru değil. Doğrusu -3 olacak.

Evet haklısınız. Ben direkt 2 sayı birbirinden farklı o zaman sonuç 1 şeklinde düşünmüştüm o an
O zaman şöyle gideyim tekrar adım adım
i = 0 -> 0^0 = 0
i = 1 -> 0^-1 = -1
i = 2 -> -1 ^ 2 = -3
i = 3 -> -3 ^0 = -3
i = 4 -> -3 ^3 = -2
i = 5 -> -2 ^5 = -5
i = 6 -> -5 ^-1 = 4
i = 7 -> 4 ^3 = 7
i = 8 -> 7 ^5 = 2.

Evet şimdi oldu. Ama benim düşündüğüm bu değildi. Muhtemelen ben algoritmayı anlamamışım tam olarak Neden böyle yapılmış xor kullanarak mantığı nedir acaba?

 

[taydin]

Tekrar eden sayılar iki tane olduğu için XOR bunları iptal ediyor (etkisiz eleman olan 0 a dönüştürüyor). Geriye de tekrar etmeyen sayı kalıyor.

 

[ozkarah]

Çok iyiymiş. Valla ne yalan söyleyeyim benim hayatta aklıma gelmezdi. Ama çok spesifik bir senaryo tabi.
Ben muhtemelen sort edip gezerdim, ya da bir hash mape ilk gelişinde ekleyip ikincisinde çıkartıtdım. Sonra kalana bakardım.

 

[taydin]

Güzel beyin cimnastiği sorusu. Ama gerçek hayatta karşılığı olabilecek bir uygulama aklıma gelmiyor.

 

[Bowman]

Evet şimdi anladım

Güzel beyin cimnastiği sorusu. Ama gerçek hayatta karşılığı olabilecek bir uygulama aklıma gelmiyor.

Ben gerçek hayattan daha çok böyle iş mülakatları vs için algoritma kurma mantığını oturtmak adına böyle soruları çözmeye çalışıyorum. Soruları çözüyorum aslında ama hep TLE (time limit exceeded) hatasına düşüyorum. Henüz ondan kurtulmanın yolunu bulamadım

 

[taydin]

Site güzelmiş ama. Ben de üye olayım da biraz soru çözeyim