Sonlar ko'paytmasi
Bu masala prefix sum texnikasining keng tarqalgan tatbiqlaridan biri. Unda siz "qo'shimcha axborotni oldindan hisoblash" g'oyasini o'rganasiz — bu ko'plab murakkab masalalarni yechishda kalit yondashuv.
Masala
Sonlar massivi berilgan. Har bir index uchun, o'sha element tashqarisidagi barcha elementlar ko'paytmasini qaytarish kerak. Ya'ni i-indexdagi javob — massivning i-element tashqarisidagi barcha sonlar ko'paytmasi.
Kirish: [1, 2, 3, 4]
Chiqish: [24, 12, 8, 6]
Tushuntirish:
javob[0] = 2 × 3 × 4 = 24 (1 tashqarisidagi barcha sonlar)
javob[1] = 1 × 3 × 4 = 12 (2 tashqarisidagi barcha sonlar)
javob[2] = 1 × 2 × 4 = 8 (3 tashqarisidagi barcha sonlar)
javob[3] = 1 × 2 × 3 = 6 (4 tashqarisidagi barcha sonlar)
Kirish: [−1, 1, 0, −3, 3]
Chiqish: [0, 0, 9, 0, 0]
Qo'shimcha shart: bo'lish amali ishlatmaslik kerak.
Nima uchun bo'lish ishlatilmaydi?
Dastlabki g'oya — barcha elementlar ko'paytmasini hisoblab, keyin har bir elementga bo'lish — ammo bu noto'g'ri. Agar massivda nol bo'lsa, bo'lish amal bajarilmaydi (nolga bo'lish). Masala ataylab bo'lishni taqiqlab, yangi yondashuv talab qiladi.
Dastlabki g'oya — ichma-ich ikki takrorlash
Har bir element uchun qolgan barcha elementlarni ko'paytiramiz:
FUNCTION kopaytma_naiv(array)
n = array uzunligi
javob = n o'lchamli massiv
FOR i = 0 DAN n - 1 GACHA
kopaytma = 1
FOR j = 0 DAN n - 1 GACHA
IF j ≠ i
kopaytma = kopaytma × array[j]
javob[i] = kopaytma
RETURN javob
Murakkablik: O(n²) vaqt. Katta massivlarda juda sekin.
Optimal yondashuv — prefix va suffix ko'paytmalar
Kuzating: javob[i] aslida ikkita qismning ko'paytmasidan iborat:
javob[i] = (0-dan i-1-gacha barcha elementlar ko'paytmasi)
× (i+1-dan n-1-gacha barcha elementlar ko'paytmasi)
Birinchi qism — chap ko'paytma (prefix product), ikkinchi qism — o'ng ko'paytma (suffix product).
Bu ikki massivni oldindan hisoblab qo'yib, ularning ko'paytmasini topish mumkin.
prefix[i] — array[0]dan array[i-1]gacha ko'paytma:
prefix[0] = 1 (chapida hech narsa yo'q)
prefix[1] = 1 (faqat array[0] = 1)
prefix[2] = 1 × 2 = 2
prefix[3] = 1 × 2 × 3 = 6
suffix[i] — array[i+1]dan array[n-1]gacha ko'paytma:
suffix[3] = 1 (o'ngida hech narsa yo'q)
suffix[2] = 4 (faqat array[3] = 4)
suffix[1] = 3 × 4 = 12
suffix[0] = 2 × 3 × 4 = 24
javob[i] = prefix[i] × suffix[i]:
javob[0] = prefix[0] × suffix[0] = 1 × 24 = 24
javob[1] = prefix[1] × suffix[1] = 1 × 12 = 12
javob[2] = prefix[2] × suffix[2] = 2 × 4 = 8
javob[3] = prefix[3] × suffix[3] = 6 × 1 = 6
Natija: [24, 12, 8, 6] ✓
FUNCTION kopaytma_prefix_suffix(array)
n = array uzunligi
prefix = n o'lchamli massiv
suffix = n o'lchamli massiv
javob = n o'lchamli massiv
prefix[0] = 1
FOR i = 1 DAN n - 1 GACHA
prefix[i] = prefix[i - 1] × array[i - 1]
suffix[n - 1] = 1
FOR i = n - 2 DAN 0 GACHA
suffix[i] = suffix[i + 1] × array[i + 1]
FOR i = 0 DAN n - 1 GACHA
javob[i] = prefix[i] × suffix[i]
RETURN javob
Murakkablik: O(n) vaqt, O(n) xotira (prefix va suffix massivlari uchun).
Xotirani optimallashtirish — O(1) qo'shimcha xotira
Prefix va suffix massivlarini saqlamasdan, natijani javob massivida to'g'ridan-to'g'ri hisoblash mumkin. Buning uchun ikki o'tish bajariladi:
1-o'tish (chapdan o'ngga): javob[i] ga prefix ko'paytmani yozamiz.
2-o'tish (o'ngdan chapga): suffix ko'paytmani bitta suffix o'zgaruvchisida saqlab, uni javob[i] ga ko'paytiramiz.
FUNCTION kopaytma_optimal(array)
n = array uzunligi
javob = n o'lchamli massiv
javob[0] = 1
FOR i = 1 DAN n - 1 GACHA
javob[i] = javob[i - 1] × array[i - 1]
suffix = 1
FOR i = n - 1 DAN 0 GACHA
javob[i] = javob[i] × suffix
suffix = suffix × array[i]
RETURN javob
Bosqichma-bosqich tahlil
[1, 2, 3, 4] uchun:
1-o'tish (prefix):
javob[0] = 1
javob[1] = javob[0] × array[0] = 1 × 1 = 1
javob[2] = javob[1] × array[1] = 1 × 2 = 2
javob[3] = javob[2] × array[2] = 2 × 3 = 6
javob = [1, 1, 2, 6]
2-o'tish (suffix):
suffix = 1, i = 3:
javob[3] = javob[3] × suffix = 6 × 1 = 6
suffix = suffix × array[3] = 1 × 4 = 4
suffix = 4, i = 2:
javob[2] = javob[2] × suffix = 2 × 4 = 8
suffix = suffix × array[2] = 4 × 3 = 12
suffix = 12, i = 1:
javob[1] = javob[1] × suffix = 1 × 12 = 12
suffix = suffix × array[1] = 12 × 2 = 24
suffix = 24, i = 0:
javob[0] = javob[0] × suffix = 1 × 24 = 24
suffix = suffix × array[0] = 24 × 1 = 24
javob = [24, 12, 8, 6] ✓
Murakkablik
| Yondashuv | Vaqt | Xotira |
|---|---|---|
| Ichma-ich ikki takrorlash | O(n²) |
O(1) |
| Prefix + suffix massivlari | O(n) |
O(n) |
| Bir o'zgaruvchi bilan | O(n) |
O(1)* |
*O(1) qo'shimcha xotira — javob massivi natija uchun kerak, u qo'shimcha xotira hisoblanmaydi.
Muhim hollar
Bitta nol: [1, 0, 3, 4]. Ko'pgina elementlar uchun javob 0 bo'ladi (chunki nol ko'paytmaga kiradi). Faqat nolning o'zi uchun javob nol bo'lmaydi — 1 × 3 × 4 = 12. Algoritm bu holatni avtomatik to'g'ri boshqaradi.
Ikkita nol: [1, 0, 0, 4]. Barcha elementlar uchun javob 0. Chunki istalgan element uchun qolganlar orasida hech bo'lmaganda bitta nol bor.
Manfiy sonlar: [−1, 2, −3]. Ko'paytma manfiy bo'lishi mumkin. Algoritm buni ham to'g'ri boshqaradi — arifmetik amallar bir xil ishlaydi.
Bitta element: [5]. Natija [1] — elementdan tashqarida hech narsa yo'q, bo'sh ko'paytma 1.
Ikki element: [3, 7]. javob[0] = 7, javob[1] = 3.
Note
Bu masalada "natija massivi" O(n) xotira talab qiladi — bu zaruriy xotira, qo'shimcha emas. Masala talab qiladigan O(1) qo'shimcha xotira degani: natijani saqlash uchun ajratiladigan xotiradan tashqari hech narsa sarflanmasin.
Qaysi texnika ishlatildi?
Bu masalada prefix va suffix oldindan hisoblash texnikasi qo'llanildi — prefix sum texnikasining ko'paytirishga moslashtirilgan varianti. G'oya bir xil: har bir elementning "chap tomoni" va "o'ng tomoni" uchun axborotni oldindan bir marta hisoblash, keyin uni O(1) da ishlatish.
Ikki o'tish (chapdan o'ngga va o'ngdan chapga) qo'shimcha xotirani O(n)dan O(1) ga tushiradi — bu ham "prefix sum" g'oyasining kuchli tatbiqi.