Analiza

Pre početka ključno je uvideti da pošto za svako ~x~ važi ~x\ \text{or}\ x = x~, a kako niz ~B~ između ostalih sadrži i rezultate operacije ili primenjene nad istim članom izvornog niza, zaključuje se da je traženi niz ~A~ zapravo podskup zadatog niza. Nameće se naivno rešenje da se formiraju svi podskupovi niza ~B~ koji sadrže tačno ~N~ članova, a zatim ispita koji tačno od njih daje zadati niz ~B~, međutim, ovo rešenje pati od izuzetno visoke vremenske složenosti.

Nije teško dalje zaključiti da rezultat ili operacije nad bitovima dva prirodna broja (operandi) nikada nije manji, već isključivo broj veći ili jednak većem operandu. Iz prethodnog lako se izvodi da su dva po vrednosti najmanja člana datog niza ~B~, označimo ih sa ~B_{S1}~ i ~B_{S2}~, sigurno i članovi izvornog niza ~A~, odnosno ~A_1 = B_{S1}~ i ~A_2 = B_{S2}~. Sledeći član izvornog niza ~A_3~ biće ili treći po vrednosti član niza ~B~, to jest ~B_{S3}~, ili pak četvrti, ~B_{S4}~, ukoliko je ~A_1\ \text{or}\ A_2 = B_{S3}~. Ponavljanjem ovog postupka, može se doći do svih članova izvornog niza, na mnogo efikasniji način od prethodno pomenutog.

Naime, u svakom koraku algoritma iz niza ~B~ treba eliminisati ili na neki način označiti sve članove koje je moguće formirati pomoću članova niza ~A~ koji su već određeni, a zatim u niz ~A~ dodati prvi sledeći po vrednosti član zadatog niza.

Smernice za algoritam

Po učitavanju članova niza ~B~ najpre je zadati niz neophodno sortirati u neopadajućem redosledu koristeći se nekim efikasnim algoritmom. Pošto niz ~B~ ne sadrži jedinstvene vrednosti, već se jedna vrednost može ponavljati više puta, u jednom prolasku kroz dobijeni sortiran niz označiti indekse kada se svaka vrednost pojavljuje prvi put. Zatim, u glavnoj petlji, prolaziti kroz sortiran zadati niz ~B~ i dodavati članove u niz ~A~, ali samo pod uslovom da taj član već nije moguće dobiti nekom kombinacijom članova koji su već dodati u niz ~A~. Da bi se ovo izvelo na efikasan način, prilikom svakog novog dodavanja u niz ~A~ proveriti i označiti sve indekse članova niza ~B~ koje je moguće formirati uparivanjem poslednje dodatog člana sa svim prethodnim koji se već nalaze u nizu ~A~. Drugim rečima moguće je koristeći se već označenim indeksima pojedinih vrednosti i njihovim inkrementiranjem znati do kog indeksa niza ~B~ je izvodljivo generisati sve članove, a zatim dodati prvi sledeći kada se do njega dođe. Ovaj proces nastaviti dok se ne prođe kroz čitav zadati niz. Kako niz ~B~ sadrži ~\frac{N(N+1)}{2}~ članova, glavna petlja ima zapravo kvadratnu složenost, odnosno ~\mathcal{O}(N^2)~. Međutim, kako je zadati niz prethodno sortiran, to će ova operacija dominirati, te je zapravo ~\mathcal{O}(N^2\log N)~ ukupna vremenska složenost ovog algoritma.