Scrii numarul N in baza 2. Vei obtine o configuratie de M (M = log N) biti. De exemplu pentru N = 25, vei obtine M = 5, iar configuratia va arata asa:
Bit[4] = 1;
Bit[3] = 1;
Bit[2] = 0;
Bit[1] = 0;
Bit[0] = 1;
Vrei sa vezi pentru fiecare pozitie i (0 <= i < M) de cate ori va aparea 1 in scrierea tuturor numerelor de la 1 la N.
Notam cu Left[ i ] numarul format de Bit[M-1], Bit[M-2], ... , Bit[i+1], iar cu Right[ i ] numarul format de Bit[i-1], Bit[i-2], ... , Bit[0]. In exemplul de mai sus, pentru i = 2, Left[2] = 3, iar Right[2] = 1. Numarul de aparitii ale lui 1 pe pozitia i in scrierea tutror numerelor de la 1 la N este:
R[i] = Left[i] * 2^i + (Bit[i] ? (Right[i]+1) : 0).
Raspunsul cautat este suma de R[ i ].