Counting Bits II

This is an extension to the previous problem counting the number of set bits or 1's present in a number.


This is an extension of the previous counting set bits problem.

Problem Statement

Write a program to return an array of number of 1’s in the binary representation of every number in the range [0, n].

Input: n = 6

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

0 --> 0
1 --> 1
2 --> 1
3 --> 2
4 --> 1
5 --> 2
6 --> 2


This is a faster execution as we use Brian Kernighan’s algorithm.

In this approach, we count only the set bits. So,

If a number has 2 set bits, then the while loop runs two times.

If a number has 4 set bits, then the while loop runs four times.



  • Outer loop runs for (n+1) time to store the number of 1 bits present every number from 0 to (n+1).
  • Inner loop uses Brian Kernighan’s algorithm to find the number of 1's present in each number


Level up your interview prep. Join Educative to access 70+ hands-on prep courses.