Primetimo, prvo, da je optimalno da moć našeg niza ima ~29~ bit ukoliko je to moguće, zato što čak i kad bi moć imala sve ostale, manje bitove, oni bi se sumirali u ~2^{29}-1~. Potom treba da proverimo da li moć može da ima i ~29~ i ~28~ bit. Ukoliko to nije moguće, ~28~ bit možemo da ignorišemo i nastavimo dalje, a ukoliko jeste, zahtevaćemo da u rešenju uvek postoje ta dva bita. Dakle, možemo da nastavimo sa ovom procedurom, pohlepnog dodavanja bitova. Neophodno je da proverimo da li možemo da nađemo podelu u ~K~ segmenata, tako da moć niza sadrži neki podskup bitova ~S~, tj. da li možemo da podelimo niz u ~K~ segmenata, tako da svaki segment sadrži bitove iz skupa ~S~. Neka su pozicije numerisane od ~0~. Pronađimo za svaku poziciju ~i~ najmanje ~j~, takvo da ~OR~ (cikličnog) segmenta ~[i,(i+j-1) mod N]~ sadrži sve bitove iz skupa ~S~. Ovakvo ~j~ možemo pronaći binarnom pretragom. Neka je ~b[i] = j~. Želeli bi da pronađemo da li je moguće napraviti podelu u segmente, tako da svaki segment sadrži bitove iz skupa ~S~ i tako da jedan segment počinje na poziciji ~i~. Tada će jedan segment početi na poziciji ~i~, naredni na poziciji ~(i+j) mod N~ itd. Ovo je moguće postići tehnikom binarnog stepenovanja (eng. ~binary~ ~lifting~). Za svaku poziciju pronađemo vrednost ~s[i][j]~ - najmanja vrednost tako da ciklični segment ~[i,(i+s[i][j]-1) mod N]~ možemo podeliti na bar ~2^j~ segmenata, tako da ~OR~ svakog segmenta sadrži sve bitove iz skupa ~S~. Tada:

• ~s[i][0] = b[i]~
• ~s[i][j] = s[i][j-1]+s[(i+s[i][j-1]) mod N][j-1] , j \geq 1~

Kada pronađemo ove vrednosti, neophodno je da pronađemo za svako ~i~ najmanje ~l~, tako da ciklični segment ~[i,(i+l-1)%n]~ možemo podeliti na ~K~ segmenata tako da ~OR~ svakog segmenta sadrži sve bitove iz skupa ~S~. To možemo pronaći na sličan način kao i vrednosti matrice ~s~. Ukoliko postoji ~i~, takvo da je ~l \leq N~, tada je moguće napraviti podelu na ~K~ segmenata tako da ~OR~ svakog segmenta sadrži sve bitove iz skupa ~S~. Složenost opisanog algoritma je ~O(N \cdot log (max A_{i}) \cdot log N)~. Zadatak je preuzet sa ~\texttt{Moscow}~ ~\texttt{Autumn}~ ~\texttt{Workshop}~ ~\texttt{2019}~ ~\texttt{Day}~ ~\texttt{1}~, takmičenje ~\texttt{Welcome}~ ~\texttt{Contest}~ ~\texttt{from}~ ~\texttt{Asia}~.