A simple O(n) solution does not need bit operations


  • 4
    K

    One simple observation on the binary representation.
    The number of 1s in the binaries of 4,5,6,7 is simply the binaries of 0,1,2,3 plus one. This is because the highest bit of them is one. (100, 101,110,111 and 000,001,010,011). So you can keep doubling result set and get results from current results without really count. 1->2->4->8->16... until you reach num.

    Bit operation is not necessary. i = i<<1 is simply i *=2;

       public int[] CountBits(int num) {
                int[] res = new int[num+1];
                int i = 1;
                res[0] = 0;
                while (i <= num)
                {
                    for (int j = 0; j < i && j + i <= num; j++)
                    {
                        res[j + i] = res[j] + 1;
                    }
                    i =i << 1;
                }
                return res;
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.