Juftsiz poyabzal (Single Number)

Butun sonlar massivi berilgan. Unda har son ikki marta uchraydi, faqat bitta son bir marta uchraydi. O'sha sonni toping.

Yechim chiziqli vaqt O(n) va doimiy xotira O(1) bilan ishlashi kerak.

Kirish: [2, 2, 1]
Chiqish: 1

Kirish: [4, 1, 2, 1, 2]
Chiqish: 4

Kirish: [1]
Chiqish: 1

Nima uchun oddiy yondashuvlar yetarli emas?

Saralash va qo'shni tekshirish: O(n log n) vaqt — qabul qilinmaydi.

Hash map bilan hisoblash: O(n) vaqt, lekin O(n) xotira — qabul qilinmaydi.

Barcha sonlar yig'indisi × 2 - massiv yig'indisi: 2 * (a + b + c) - (a + a + b + b + c) = c. Lekin katta sonlarda overflow xavfi va u ham formula bo'lgani uchun O(1) xotira bo'lsa ham, XOR usuli yanada elegantroq.

Sharti: O(n) vaqt va O(1) xotira. Bu XOR ning asl maydoni.

Asosiy g'oya: XOR xossalari

XOR ning ikki muhim xossasini eslaylik:

a ^ a = 0       // bir xil son o'zi bilan XOR → 0
a ^ 0 = a       // 0 bilan XOR → o'zgarish yo'q
XOR kommutativ va assotsiativ

Massivdagi barcha elementlarni ketma-ket XOR qilsak:

[4, 1, 2, 1, 2]

4 ^ 1 ^ 2 ^ 1 ^ 2
= 4 ^ (1 ^ 1) ^ (2 ^ 2)   // kommutativlik va assotsiativlik bilan qayta tartiblanadi
= 4 ^ 0 ^ 0
= 4

Har ikki marta uchragan son o'zi bilan XOR qilinganda 0 ga aylanadi. Faqat bir marta uchragan son qoladi.

Pseudocode

FUNCTION SINGLE_NUMBER(nums)
    result = 0
    FOR har bir num nums ichida
        result = result XOR num
    RETURN result

Hammasi shu. Hech qanday qo'shimcha xotira kerak emas.

Bosqichma-bosqich dry run

nums = [4, 1, 2, 1, 2]:

result = 0

num = 4: result = 0 ^ 4 = 4
num = 1: result = 4 ^ 1 = 5     (0100 ^ 0001 = 0101)
num = 2: result = 5 ^ 2 = 7     (0101 ^ 0010 = 0111)
num = 1: result = 7 ^ 1 = 6     (0111 ^ 0001 = 0110)
num = 2: result = 6 ^ 2 = 4     (0110 ^ 0010 = 0100)

RETURN 4

nums = [2, 2, 1]:

result = 0

num = 2: result = 0 ^ 2 = 2
num = 2: result = 2 ^ 2 = 0
num = 1: result = 0 ^ 1 = 1

RETURN 1

Vaqt va xotira murakkabligi

Xususiyat	Qiymat	Izoh
Vaqt	O(n)	Massiv bir marta ko'riladi
Xotira	O(1)	Faqat result o'zgaruvchisi

Edge case'lar

Bitta element. [7] → 0 ^ 7 = 7.

Massiv tartibsiz. XOR kommutativ va assotsiativ — tartib muhim emas.

Salbiy sonlar. XOR ishorali sonlarda ham to'g'ri ishlaydi — bit darajasida amal.

Katta sonlar. 32-bit chegarasida xotira yoki overflow muammosi yo'q.

Note

Bu masala "ikkita yoki ko'proq marta takrorlanuvchi sonlar" variantlarida kengayadi. Masalan, "har son uch marta uchraydi, bittasi bir marta" — bu holat oddiy XOR bilan ishlamaydi, bit darajasida modular arifmetika kerak. "Ikkita son bir marta uchraydi" — XOR bilan ikki guruhga ajratish kerak.

Masalaning kengaytirilgan variantlari

Har son uch marta uchraydi (Single Number II)

Oddiy XOR ishlamaydi. Har bit uchun uchlik hisoblash:

FUNCTION SINGLE_NUMBER_II(nums)
    ones  = 0
    twos  = 0
    FOR har bir num nums ichida
        ones  = (ones XOR num) AND (NOT twos)
        twos  = (twos XOR num) AND (NOT ones)
    RETURN ones

ones — bir marta, twos — ikki marta ko'rilgan bitlar. Uch marta ko'rilganda ikkala to'plamdan ham chiqariladi.

Ikkita son bir marta uchraydi (Single Number III)

FUNCTION SINGLE_NUMBER_III(nums)
    xor_all = 0
    FOR har bir num nums ichida
        xor_all = xor_all XOR num
    // xor_all = a XOR b (a va b — bir marta uchraganlar)
    // xor_all da kamida bitta 1 bit bor — a va b farqlangan pozitsiya
    diff_bit = xor_all AND (-xor_all)   // eng quyi 1 bit

    a = 0
    FOR har bir num nums ichida
        IF num AND diff_bit ≠ 0
            a = a XOR num   // shu bitga ko'ra guruhga ajratish

    b = xor_all XOR a
    RETURN [a, b]

Xulosa

Juftsiz son — XOR ning a ^ a = 0 xossasining klassik qo'llanishi. Barcha elementlarni XOR qilish: juft takrorlaganlar 0 ga aylanib bekor bo'ladi, yolg'iz qolgan son natijaviy qiymatda saqlanadi.

O(n) vaqt, O(1) xotira — ikkala shart ham bajariladi. Massiv tartibi muhim emas — XOR kommutativ.