Counting Bits O(n) Solution – LeetCode [Easy] | Brian Kernighan’s Algorithm

Problem

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1‘s in the binary representation of i.

LeetCode Problem Link

Input

Integer n

Output

array ans of length n+1, where ans[i] is the number of 1’s in the binary representation of i

Constraints

• 0 <= n ≤ 10⁵

Sample Input

n = 2

Sample Output

[0, 1, 1]

Explanation
0 --> 0
1 --> 1
2 --> 10

Solution

Requirements: linear time O(n) solution and in a single pass

Approach:
Brian Kernighan’s Algorithm
If we subtract a number n by 1 and do it bitwise & with itself (n & (n-1)), we unset the rightmost set bit of number n. For example:

8 in binary is 1000 
7 in binary is 0111 
8&7 = 0000 (4th (right most) bit is unset)

3 in binary is 011 
2 in binary is 010 
3&2 = 010 (1st (right most) bit is unset)

So, the number of 1s in its binary representation also decreases by one. So number of 1s in n will be 1s in number (n&(n-1)) + 1. The idea is to store the number of 1s in binary representation of i (0 <= i <= n) in bottom up manner.

Code Implementation

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> sol(num+1, 0);
        
        //Brian Kernighan’s Algorithm
        for (int i=1; i<=num; i++) {
            sol[i] = sol[i&(i-1)]+1;
        }
        
        return sol;
    }
};

Time complexity: O(n)