Analiza

Primetimo da ako zbir svih elemenata niza nije deljiv brojm ~L~, onda ne postoji rešenje, jer se niz ne može podeliti u ~L~ grupa koji imaju jednake zbirove. Znači u tom slučaju je rešenje nula (0). Ako je ~S~ zbir svih elemenata niza ~S~ i ako je ~S~ deljivo brojem ~L~, onda zbir svake od grupa mora biti ~S/L~. Neka je ~L'~ broj grupa za koje važi da je zbir različit od ~S/L~. Tada važi sledeće: Ako ~L'\not\in\{0,2\}~, onda ne postoji niti jedna razmena kojom bi se izjednačio zbir elemenata u svim grupama, pa je rešenje nula. Ako je ~L'=0~, onda sve grupe već imaju jednak zbir, pa zbog toga razmena bilo kog para elemenata iz iste grupe ili bilo kog para elemenata koji imaju istu vrednost dovodi do niza koji zadovoljava uslov (da sve grupe imaju isti zbir). Broj razmena u kojima se razmenjuju elementi iz iste grupe je \(None\) L \times \frac{N/L(N/L-1)}{2}. \(None\) Broj razmena u kojima se razmenjuju jednaki elementi se dobija tako što se prebroji broj pojavljivanja svake od vrednosti. Ako su ~V_1, V_2, V_3, ..., V_K~ različite vrednosti koji se pojavljuju u nizu ~a~, a ~n_{V_1}, n_{V_2}, n_{V_3}, ..., n_{V_K}~, brojevi pojavljivanja tih vrednosti onda je broj razmena elemenata koji imaju istu vrednost jednak: \(None\) \frac{n_{V_1}(n_{V_1}-1)}{2} + \frac{n_{V_2}(n_{V_2}-1)}{2} + ... + \frac{n_{V_K}(n_{V_K}-1)}{2}. \(None\) Međutim, u ovom izrazu figurišu i razmene jednakih koji se nalaze u istoj grupi. Zbog toga te razmene treba oduzeti, a to ćemo izvesti tako što ćemo isti postupak prebrajanja vrednosti izvesti za svaku grupu i izračunati vrednost odgovarajućeg izraza (ekvivalentnog gornjem). Ako je ~L'=2~, onda postoje dve grupe u kojima se zbir ne poklapa sa prosečnom vrednošću (tj. sa ~S/L~). U jednoj grupi je zbir veći od proseka, a u drugoj je manji od proseka (pri čemu su apsolutne razlike tih suma i proseka jednake). Označimo sa ~d~ apsolutnu razliku sume jedne od tih grupa i proseka ~S/L~. Tada se može razmeniti bilo koji par elemenata iz te dve grupe za koji važi da je razlika elementa koji se nalazi grupi sa većim zbirom i elementa koji se nalazi u grupi u kojoj je manji zbir jednak ~d~. Znači, potrebno je prebrojati broj pojavljivanja pojedinih vrednosti u dve grupe, nakon toga izmnožiti odgovarajuće brojeve pojavljivanja i proizvode sabrati.

Smernice za algoritam

Budući da su vrednosti elementa manje od ili jednake ~10^6~, može se formirati niz u kome će se računati brojevi pojavljivanja pojedinih vrednosti. Zbog toga brojeve pojavljivanja pojedinih vrednosti možemo odrediti jednim prolazom kroz niz. Pored toga potreban je jedan prolaz kroz niz kako bi se odredili zbirovi elemenata po grupama. Ali kako se u oba slučaja radi o jednom prolazu kroz niz, algoritam ima linearnu složenost.