Counting bits

Mar 21, 2021

medium

Given a non-negative integer number num. For every number 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:

Input: 2
Output: [0,1,1]

Example 2:

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

Code

public int[] countBits(int num) {
  int[] dp = new int[num + 1];
  for (int i = 0; i <= num; i++) {
    if (num & 1 == 0) { // even
      dp[i] = dp[i >> 1]; 
    } else {
      dp[i] = dp[i - 1] + 1; 
    }
  }
  return dp;
}

Intuition

How do we get the result at dp[i] based on previous results?

There are two cases:

When the number i is even, the least significant bit is 0. If we right shift i by 1, we effectively drop the trailing 0, and the set bit count remains the same.
When the number i is odd, compare it with the previous number, which is even. Numerically, i is 1 greater than i - 1, and the set bit count is also 1 greater.

0  | 0000 0000
1  | 0000 0001
2  | 0000 0010
3  | 0000 0011
4  | 0000 0100
5  | 0000 0101

Reference

How we handle this question on interview [Thinking process + DP solution] - LeetCode Discuss