Reference: LeetCode
Difficulty: Medium

Problem

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.

Example: 

1
2
3
4
Input: 2
Output: [0,1,1]
Input: 5
Output: [0,1,1,2,1,2]

Follow up:

  • It is very easy to come up with a solution with runtime $O(n \times \text{sizeof}(\text{int}))$. But can you do it in linear time $O(n)$ / possibly in a single pass?
  • Space complexity should be $O(n)$.
  • Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in C++ or in any other language.

Analysis

Methods:

  1. Brute-Force

    • For each value, count the number of bits.
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      public int[] countBits(int num) {
        int[] ret = new int[num + 1];
        for (int i = 0; i <= num; ++i) {
          ret[i] = numberOfOneBits(i);
        }
        return ret;
      }

      private int numberOfOneBits(int n) {
        int count = 0;
        while (n != 0) {
          count += 1;
          n = n & (n - 1);
        }
        return count;
      }
      Time: $O(NM)$. $M$ is the number of bits.
      Space: $O(N)$

  2. DP + Least Significant Bit

    • We can observe that for a digit abcd in binary form, a transition function could be:
    • dp[abcd] = dp[abc] + dp[d] = dp[abc >>> 1] + (d & 1). 
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      //  val    binary    #num
      //    0         0      0  dp[0] = dp[00] = 0
      //    1         1      1  dp[1] = dp[01] = 1
      //    2        10      1  dp[2] = dp[10] = 1
      //    3        11      2  dp[3] = dp[11] = 2 = dp[01] + dp[10] = 1 + 2
      //    4       100      1  dp[4] = dp[100] = 1
      //    5       101      2  dp[5] = dp[101] = 2 = dp[10] + dp[1]
      //    6       110      2  dp[6] = dp[110] = 2 = dp[11] + dp[0]
      //    7       111      3  dp[7] = dp[111] = 3 = dp[val >>> 1] + dp[val & 1]
      public int[] countBits(int num) {
        int[] dp = new int[num + 1];
        for (int val = 0; val <= num; ++val) {
          dp[val] = dp[val >>> 1] + (val & 1);  // dp[val & 1]
        }
        return dp;
      }
      Time: $O(N)$
      Space: $O(N)$

  3. DP + Most Significant Bit

    • I think this one is less elegant.
    • Reference:link
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      public int[] countBits(int num) {
        int[] dp = new int[num + 1];
        for (int i = 0; i <= num; ++i) {
          int msb = locateMSB(i);
          dp[i] = dp[i ^ msb] + ((msb > 0) ? 1 : 0); // turn off the msb
        }
        return dp;
      }

      public int locateMSB(int val) {
        while ((val & (val - 1)) != 0) {
          val &= (val - 1);
        }
        return val;
      }
      Time: $O(N \times \text{sizeof}(int))$
      Space: $O(N)$

  4. DP + Last Set Bit

  • With the same logic as previous approaches, we can also do it with the last set bit. For x, we have:
  • dp[x] = dp[x & (x - 1)] + 1
  • Note: loop should start from 1 since dp[0] = dp[0 & -1] + 1 = 1. 
    1
    2
    3
    4
    5
    6
    7
    public int[] countBits(int num) {
      int[] dp = new int[num + 1];
      for (int val = 1; val <= num; ++val) {
        dp[val] = dp[val & (val - 1)] + 1;
      }
      return dp;
    }
    Time: $O(N)$
    Space: $O(N)$