Counting Bits

Problem Statement

LeetCode-338: Given an integer n, return an array ans of length n + 1 such that for each i $(0 \leq i \leq n)$, ans[i] is the number of 1’s in the binary representation of i.

Example 1:

Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10

Example 2:

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

Approach

We’ll be focusing on two approaches to solve the problem.

• Brian Kernighan’s algorithm
• Dynamic Programming

Approach 1: Brian Kernighan’s Algorithm

The algorithm is based on the observation that for any number n, n & (n - 1) unsets the rightmost set bit. We can use this observation to count the number of set bits in a number.

High level steps include:

1. For every number i from 0 to n, we’ll calculate the number of set bits in the binary representation of i.
2. For this, we’ll initialize a variable freq to 0.
3. We’ll keep unsetting the rightmost set bit of i until i becomes 0. This can be done by i = i & (i - 1).
4. We’ll increment the freq variable every time we unset a bit.
5. The value of freq will be the number of set bits in the binary representation of i.
6. Populate the result array with the value of freq.

Approach 2: Dynamic Programming

We can solve the problem using dynamic programming. We can define a recurrence relation for the problem as follows:

$$ ans[i] = ans[i/2] + (i \ mod \ 2) $$

This is based on the observation that the number of set bits in a number i is equal to the number of set bits in i/2 plus the least significant bit of i.

Consider the following example to calculate the number of set bits in i=5:

Consider i=5, i.e. 101 in binary representation which have 2 set bits:
ans[5] = ans[5/2] + (5 % 2)
       = ans[2] + 1
       = 1 + 1
       = 2

Implementation

Here is a java implementation of the above approaches. Let’s first look at the implementation of Brian Kernighan’s algorithm:

public int[] countBits(int n) {
    int [] ans = new int[n+1];
        
    for(int i=0; i <= n; i++){
        int freq=0;
        int x = i;
        while(x != 0){
            freq++;
            x=x&(x-1);
        }
        ans[i]=freq;
    }

    return ans;
}

And here is the implementation of the dynamic programming approach:

public int[] countBits(int n) {
    int[] ans = new int[n+1];
    for(int i=1; i <= n ; i++){
        // ans[i/2] + (i % 2)
        ans[i] = ans[i >> 1] + (i & 1);
    }  
    return ans;
}

Complexity Analysis

For the first approach, the time complexity is $O(n \cdot \log n)$ and the space complexity is $O(n)$. This is because the number of bits in n equals to $log\ n+1$ and in worst case, all the bits can be equal to 1, and we will be repeating the operation for all the numbers in range 0 to n.

For the second approach, the time complexity is $O(n)$ and the space complexity is $O(n)$.