Summary

This article is for intermediate readers. It relates to the following ideas:\nPop Count, Most Significant Bit, Least Significant Bit, Last Set Bit and Dynamic Programming.

Solutions

Approach #1 Pop Count [Accepted]

Intuition

Solve the problem for one number and applies that for all.

Algorithm

This problem can be seen as a follow-up of the Problem 191 The number of 1 bits. It counts the bits for an unsigned integer. The number is often called pop count or Hamming weight. See the editorial of Problem 191 The number of 1 bits for a detailed explanation of different approaches.

Now we just take that for granted. And suppose we have the function int popcount(int x) which will return the count of the bits for a given non-negative integer. We just loop through the numbers in range [0, num] and put the results in a list.

Complexity Analysis

\n
• \n

  Time complexity : $$O(nk)$$ . For each integer $$x$$ , we need $$O(k)$$ operations where $$k$$ is the number of bits in $$x$$ .

  \n
\n
• \n

  Space complexity : $$O(n)$$ . We need $$O(n)$$ space to store the count results. If we exclude that, it costs only constant space.

  \n
\n

Approach #2 DP + Most Significant Bit [Accepted]

Intuition

Use previous count results to generate the count for a new integer.

Algorithm

Suppose we have an integer:

\n $$\nx = (1001011101)_2 = (605)_{10}\n$$ \n

and we already calculated and stored all the results of $$0$$ to $$x - 1$$ .

Then we know that $$x$$ is differ by one bit with a number we already calculated:

\n $$\nx\' = (1011101)_2 = (93)_{10}\n$$ \n

They are different only in the most significant bit.

Let\'s exam the range $$[0, 3]$$ in the binary form:

\n $$\n(0) = (0)_2\n$$ \n

\n $$\n(1) = (1)_2\n$$ \n

\n $$\n(2) = (10)_2\n$$ \n

\n $$\n(3) = (11)_2\n$$ \n

One can see that the binary form of 2 and 3 can be generated by adding 1 bit in front of 0 and 1. Thus, they are different only by 1 regarding pop count.

Similarly, we can generate the results for $$[4, 7]$$ using $$[0, 3]$$ as blueprints.

In general, we have the following transition function for popcount $$P(x)$$ :

\n $$\nP(x + b) = P(x) + 1, b = 2^m > x\n$$ \n

With this transition function, we can then apply Dynamic Programming to generate all the pop counts starting from $$0$$ .

public class Solution {\n    public int[] countBits(int num) {\n        int[] ans = new int[num + 1];\n        int i = 0, b = 1;\n        // [0, b) is calculated\n        while (b <= num) {\n            // generate [b, 2b) or [b, num) from [0, b)\n            while(i < b && i + b <= num){\n                ans[i + b] = ans[i] + 1;\n                ++i;\n            }\n            i = 0;   // reset i\n            b <<= 1; // b = 2b\n        }\n        return ans;\n    }\n}\n

Complexity Analysis

\n
• \n

  Time complexity : $$O(n)$$ . For each integer $$x$$ we need constant operations which do not depend on the number of bits in $$x$$ .

  \n
\n
• \n

  Space complexity : $$O(n)$$ . We need $$O(n)$$ space to store the count results. If we exclude that, it costs only constant space.

  \n
\n

Approach #3 DP + Least Significant Bit [Accepted]

Intuition

We can have different transition functions, as long as $$x\'$$ is smaller than $$x$$ and their pop counts have a function.

Algorithm

Following the same principle of the previous approach, we can also have a transition function by playing with the least significant bit.

Let look at the relation between $$x$$ and $$x\' = x / 2$$ \n

\n $$\nx = (1001011101)_2 = (605)_{10}\n$$ \n

\n $$\nx\' = (100101110)_2 = (302)_{10}\n$$ \n

We can see that $$x\'$$ is differ than $$x$$ by one bit, because $$x\'$$ can be considered as the result of removing the least significant bit of $$x$$ .

Thus, we have the following transition function of pop count $$P(x)$$ :

\n $$\nP(x) = P(x / 2) + (x \\mod 2)\n$$ \n

Complexity Analysis

\n
• \n

  Time complexity : $$O(n)$$ . For each integer $$x$$ we need constant operations which do not depend on the number of bits in $$x$$ .

  \n
\n
• \n

  Space complexity : $$O(n)$$ . Same as approach #2.

  \n
\n

Approach #4 DP + Last Set Bit [Accepted]

Algorithm

With the same logic as previous approaches, we can also manipulate the last set bit.

Last set bit is the rightmost set bit. Setting that bit to zero with the bit trick, x &= x - 1, leads to the following transition function:

\n $$\nP(x) = P(x \\mathrel{\\&} (x - 1)) + 1;\n$$ \n

Complexity Analysis

\n
• \n

  Time complexity : $$O(n)$$ . Same as approach #3.

  \n
\n
• \n

  Space complexity : $$O(n)$$ . Same as approach #3.

  \n
\n