This question has already been answered:

There is a set of positive integers from 0..N.

It is necessary for O (N) to count the number of units of each number in the binary representation and put this info into the array!

Perhaps the question does not make sense, but you can do it quickly, instead of calculating the number of units of each number as a logarithm and get N log 14 (14 because the numbers do not exceed 10 ^ 4), you just need to do it in N.

Reported as a duplicate by Nick Volynkin ♦ Mar 6 '17 at 6:43 .

A similar question was asked earlier and an answer has already been received. If the answers provided are not exhaustive, please ask a new question .

  • four
    Is it nothing that O (N * log 14) is exactly the same as O (N)? - Yaant

1 answer 1

Consider the beginning of the table of numbers of bits:

Число Бит 0 0000 0 1 0001 1 2 0010 1 3 0011 2 4 0100 1 5 0101 2 6 0110 2 7 0111 3

You may notice that each degree 2 adds one high bit, and the rest go the same way as in the entire previous table. So we can build a table based on it itself, by correctly choosing the offset of the previous table element from which to take the quantity. When N is a power of 2 (N & (N-1) is zero), you must start again from the beginning of the table.

 int BITS[1024]; int main(){ int N,offs; BITS[0]=0; for(N=1;N<1024;N++) { if(! (N & (N-1)) ) offs=N; BITS[N]=BITS[N-offs]+1; } }