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)$

  1. 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)$

  1. 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)$

  1. 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)$


Comment