Unutilgan son

0 dan n gacha bo'lgan n + 1 ta sondan tuzilishi kerak bo'lgan massiv berilgan, lekin unda faqat n ta son bor. Ya'ni bitta son yo'q. Yo'qolgan sonni toping.

Massivda takroriy element yo'q. Har son [0, n] oralig'idan.

Kirish: [3, 0, 1]
n = 3, son = 3, oraliq = [0,1,2,3]
Chiqish: 2

Kirish: [0, 1]
n = 2, son = 2, oraliq = [0,1,2]
Chiqish: 2

Kirish: [9, 6, 4, 2, 3, 5, 7, 0, 1]
n = 9, oraliq = [0..9]
Chiqish: 8

Birinchi yondashuv: yig'indi formulasi

0 dan n gacha bo'lgan barcha sonlar yig'indisi aniq ma'lum:

kutilgan_yigindi = n × (n + 1) / 2

Massivdagi sonlar yig'indisini hisoblab, kutilgandan ayirsak — yo'qolgan son chiqadi:

yo'qolgan = kutilgan_yigindi - haqiqiy_yigindi

FUNCTION MISSING_NUMBER_SUM(nums)
    n               = LENGTH(nums)
    kutilgan        = n * (n + 1) / 2
    haqiqiy_yigindi = YIGINDI(nums)
    RETURN kutilgan - haqiqiy_yigindi

Dry run

nums = [3, 0, 1]:

n = 3
kutilgan = 3 * 4 / 2 = 6
haqiqiy  = 3 + 0 + 1 = 4
yo'qolgan = 6 - 4 = 2

Murakkablik

• Vaqt: O(n) — yig'indi hisoblash
• Xotira: O(1)

Cheklov

Katta n da n * (n + 1) overflow qilishi mumkin. 32-bit sonda n > 65535 bo'lsa n * (n + 1) INT_MAX dan oshadi. 64-bit sonda bu muammo yo'q.

Ikkinchi yondashuv: XOR hiylaklari

XOR xossalarini eslaymiz:

a ^ a = 0
a ^ 0 = a
XOR kommutativ va assotsiativ

Agar 0 dan n gacha barcha sonlar va massivdagi barcha sonlarni XOR qilsak, takroriy sonlar bir-birini bekor qiladi, faqat yo'qolgan son qoladi:

FUNCTION MISSING_NUMBER_XOR(nums)
    n      = LENGTH(nums)
    result = n   // n ni ham qo'shamiz chunki u kutilgan qatorda bor

    FOR i = 0 DAN n - 1 GACHA
        result = result XOR i XOR nums[i]

    RETURN result

Nima sodir bo'ladi:

result = n XOR 0 XOR nums[0]
           XOR 1 XOR nums[1]
           ...
           XOR (n-1) XOR nums[n-1]

[0, n] dagi har son ikki marta (bir marta i sifatida, bir marta nums[i] sifatida) XOR qilinadi — nolga teng. Faqat yo'qolgan son i sifatida XOR qilinadi, nums[i] sifatida yo'q — u qoladi.

Dry run

nums = [3, 0, 1]:

n = 3, result = 3

i=0: result = 3 ^ 0 ^ nums[0] = 3 ^ 0 ^ 3 = 0
i=1: result = 0 ^ 1 ^ nums[1] = 0 ^ 1 ^ 0 = 1
i=2: result = 1 ^ 2 ^ nums[2] = 1 ^ 2 ^ 1 = 2

RETURN 2

Qadamma-qadam ko'ramiz: 3 ^ 3 = 0, 0 ^ 0 = 0, 1 ^ 1 = 0, 2 qoladi.

Murakkablik

• Vaqt: O(n)
• Xotira: O(1)
• Overflow xatari yo'q

Uchinchi yondashuv: to'plam (set)

[0, n] dan qaysi son massivda yo'qligini set bilan topish:

FUNCTION MISSING_NUMBER_SET(nums)
    n       = LENGTH(nums)
    seen    = SET(nums)
    FOR i = 0 DAN n GACHA
        IF i seen ichida yo'q
            RETURN i
    RETURN -1   // bu yerga yetilmaydi

• Vaqt: O(n)
• Xotira: O(n) — set uchun

Bu yondashuvning afzalligi — kodni o'qish oson. Kamchiligi — O(n) xotira.

Yondashuvlar taqqoslanishi

Yondashuv	Vaqt	Xotira	Overflow xatari
Yig'indi formulasi	O(n)	O(1)	Katta n da
XOR	O(n)	O(1)	Yo'q
Set	O(n)	O(n)	Yo'q

Amalda XOR yondashuvi — optimal: O(n) vaqt, O(1) xotira, overflow xatari yo'q.

Edge case'lar

nums = [0]: n=1, kutilgan = 1, haqiqiy = 0. Yo'qolgan = 1.

nums = [1]: n=1, kutilgan = 1, haqiqiy = 1. Yo'qolgan = 0.

Yo'qolgan son n ning o'zi. Masalan nums = [0, 1, 2] — yo'qolgan son 3. Yig'indi: 6 - 3 = 3. XOR: n=3 boshidan qo'shiladi, shuning uchun to'g'ri ishlaydi.

Bitta element. nums = [0] → 1, nums = [1] → 0.

Note

Masalada takroriy element yo'q deb kafolat berilgan. Agar takroriy bo'lsa — yig'indi formulasi ham, XOR ham noto'g'ri natija beradi. Bunday holatda set yondashuvi yoki saralash kerak bo'ladi.

Xulosa

Unutilgan son uchta yondashuv bilan yechiladi: yig'indi formulasi (O(1) xotira, overflow xavfi), XOR (O(1) xotira, overflow yo'q), set (O(n) xotira).

XOR yondashuvi eng universal: overflow yo'q, xotira minimal. Asosi — a ^ a = 0 xossasi: takroriy sonlar bekor qilinadi, yo'qolgan son qoladi.