# 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.

Integer n

#### Output

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

• 0 <= n ≤ 105

#### 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.

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)