Data Structure

Count total set bits in numbers from 0 to N

Problem Statement: Given an array of N+1 integers from 0 to N, return an array of length N + 1 which contains the count of set bits in present in all of the numbers from 0…N

Note: Can you do this in O(N) without using GCC’s builtin popcount (__builtin_popcount)?

Example 1:

Input Format: N = 2

Result: [0, 1, 1]

Explanation: 
Binary Representations of numbers from 0 to 2
0 = 0
1 = 1
2 = 10

Example 2:

Input Format: N = 5

Result: [0, 1, 1, 2, 1, 2]

Explanation:
Binary Representations of numbers from 0 to 5
0 = 0
1 = 1
2 = 10
3 = 11
4 = 100
5 = 101

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution 1 [Kernighan’s bit count algorithm]

Intuition: This method devised by Brian W. Kernighan is a fast, consistent way to count the number of bits used by integers of varying word sizes. This was devised in times where computer architecture wasn’t standardized leading to this variation. To find the number of bits in a number, we must count the number of steps taken to go from x to 0 by turning the maximum number of the rightmost bits off in a step. Where x is a number in the range [0, N].

Approach: This will be done by the bitwise-and operation between x and x – 1. This is similar to the 2 line solution to the Power of 2 problem, except here we use it iteratively and we re-use the result of each iteration. We can make this into a function that will result in something like this. 

int getBits(int x) {
        int count = 0;
        while (x) {
            x &= x - 1;
            count++;
        }
        return count;
    }

Dry Run: We are going to do this for one number as it will be the same for the other numbers within the valid range. Let’s take x = 10 for example, in each iteration

  1. 10 [1010] & 9 [1001] = 8 [1000]   
    1. count = 1 
    2. x = 8
  2. 8 [1000] & 7 [0111] = 0 [0000]
    1. count = 2
    2. x = 0

This will return 2 which is correct.

Code:

C++ Code

class Solution {

private:
    int getBits(int x) {
        int count = 0;
        while (x) {
            x &= x - 1;
            count++;
        }
        return count;
    }

public:
    vector<int> countBits(int n) {
        vector<int> res;
        for (int x = 0; x <= n; x++)
            res.push_back(getBits(x));
        return res;
    }
};

Time Complexity: O(n log(n)), because one needs log₂(n) bits to represent the number n.

Space Complexity: O(n)

Solution 2 [Lookup using bit pattern with Dynamic Programming]

Intuition: This was developed with the pattern noticed while representing numbers up to 16 in their binary forms. I would highly suggest you do the same, write on a piece of paper the binary representation of numbers from 0 to 16, you will notice 2 things.

  1. Every even number (n) has the same amount of bits as (n/2).
  2. Every odd number (n) has the amount of bits as (n/2) + 1.

Approach: This is rather straightforward, iterate from 1 to N, and for each iteration, use

res[x] = res[x/2] + (x % 2);

Where x is within the range [1, N]. Here, 0 is excluded as the resultant array is initialized with 0.

Dry Run: Let’s take n = 7 as an example, in each iteration

  1. When x = 1
    1. res[1] = res[0] + 1
    2. res[1] = 0 + 1 = 1
  2. When x = 2
    1. res[2] = res[1] + 0
    2. res[2] = 1 + 0 = 1
  3. When x = 3
    1. res[3] = res[1] + 1
    2. res[3] = 1 + 1 = 2
  4. When x = 4
    1. res[4] = res[2] + 0
    2. res[4] = 1 + 0 = 1
  5. When x = 5
    1. res[5] = res[2] + 1
    2. res[5] = 1 + 1 = 2
  6. When x = 6
    1. res[6] = res[3] + 0
    2. res[6] = 2 + 0 = 2
  7. When x = 7
    1. res[7] = res[3] + 1
    2. res[7] = 2 + 1 = 3

The resultant array will be [0, 1, 1, 2, 1, 2, 3] which is correct.

Code:

C++ Code

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> res(n + 1, 0);
        for (int x = 1; x <= n; x++)
            res[x] = res[x / 2] + (x % 2);
        return res;
    }
};

Time Complexity: O(n), since lookups in an array take constant time

Space Complexity: O(n)

Special thanks to Apan Trikha for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article