Counting Bits

Patrick Leaton
Published: June 3, 2021, 4:06 a.m.
Problem Description

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:

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

Example 2:

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

Follow up:

  • It is very easy to come up with a solution with run time O(n*sizeof(integer)). 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.

 

The description was taken from https://leetcode.com/problems/counting-bits/.

Problem Solution

#O(N) Time, O(N) Space

class Solution:
    def countBits(self, num: int) -> List[int]:
        dp = [0]*(num+1)
        for i in range(1, num+1):
            dp[i] = dp[i &(i-1)] + 1
        return dp

Problem Explanation

In Number of 1 Bits, we went over a trick to count bits by continuously using an AND operator on the number and the number minus one.  This flips the least significant bit in the number to zero, so we just needed to count how many iterations it took to make the number zero.

Here, we will be doing a similar approach, but we will be saving the result for each subproblem from one to n. 

This way, we don't have to keep recalculating values.

We can solve this by creating a dp array to cache previously calculated values and build upon those subproblem answers to get a bottom-up solution.

We will start by creating our dp array.

This array will hold the answers to each subproblem. 

        dp = [0]*(num+1)

 

Then for each iteration, we will ask how many bits are in the binary number equal to the current index.

This would start from index one since there are zero bits in the number zero.

        for i in range(1, num+1):
            dp[i] = dp[i &(i-1)] + 1
 

The way we can calculate this is by referring to the answers to the previous subproblems for the previous indices.

For example, let's say we are trying to calculate how many bits are in the binary number three.

We would lookup in our dp array how many bits were in the index number without the last set bit, get that answer in constant time and just add back the last bit, then we'd mark the index with that many bits.  The calculation would look like this:

dp[3] = dp[3 &(3-1)] + 1

dp[3] = dp[0011 & 0010] + 1

dp[3] = dp[0010] + 1, dp[2] = 1

dp[3] = 1+1

dp[3] = 2

        for i in range(1, num+1):
            dp[i] = dp[i &(i-1)] + 1

 

Once we have finished calculating each binary value, we will return the dp array.

        return dp