Nalazenje svih parova brojeva ...

Da li je neko negde naisao na sledeci za****k, odnosno njegovo resenje:

Dat je niz celih brojeva a=(a1,a2,...,an). Konstruisati algoritam slozenosti
manje od O(n^2) za nalazenje svih parova (i,j) takvih da se binarni zapisi
brojeva ai i aj ne razlikuju na vise od 2 mesta.

Nisam siguran da si lepo postavio zadakat.

Samo da bi ispisao sve kombinacije kojih moze biti O(n²) treba ti O(n²) vremena.

Trivijalni algoritam proverava svaki broj sa svakim brojem
i tu imamo slozenost O(n^2).

Ako skoro svi brojevi zadovoljavaju trazeni uslov onda je
opet slozenost O(n^2).

Ali ako malo brojeva recimo k (k << n) zadovoljava trazeni
uslov onda bi nekim efikasnijim algoritmom od trivijalnog za
te slucajeve slozenost bila manja od O(n^2), a u slucaju
kad skoro svi brojevi zadovoljavaju uslov onda bi naravno i
slozenost efikasnijeg algoritma od trivijalnog isto bila O(n^2).

Znaci problem bi bio naci algoritam koji je efikasan za
slucajeve sa malo brojeva koji zadovoljavaju uslov zadatka
i za te slucajeve ima manju slozenost od O(n^2).