Count Set Bits In First N Natural Numbers
1. You are given a number n.Input Format
2. You have to print the count of set bits of first n natural numbers.
A number nOutput Format
A numberQuestion Video
1 <= n <= 10^9Sample Input
17Sample Output
35

Editorial
The problem here deals with counting the set bits for the first N natural numbers.
A brute force approach can be to traverse from 1 to N and for every integer count the number of set bits using Kerninghams algorithm and add that to the result.
Now let us try to optimize the solution. For that let us try to approach the solution with the help of an example:
N = 11
Binary Representation of Numbers from 0 to 11
0 > 0 0 0 0
1 > 0 0 0 1
2 > 0 0 1 0
3 > 0 0 1 1
4 > 0 1 0 0
5 > 0 1 0 1
6 > 0 1 1 0
7 > 0 1 1 1

8 > 1 0 0 0
9 > 1 0 0 1
10 > 1 0 1 0
11 > 1 0 1 1
Now we wish to calculate all the bits which are having a value of 1 in this set of binary numbers. If we observe the numbers from 0 7 then they are a complete set for a 3bit number which means that it contains all the arrangements of the bits for a size of 3, this also implies that for every bit position the bit has been valued 0 and 1 equally so for a length of 8 the number of set bits becomes 8/2 + 8/2 + 8/2 = 12 = 231 * 3 = 2x1 * x where x represents the highest power of 2 so that 2x is less than or equal to N.
Also after a complete set of 3bits, the values at the lower 3 bits tend to repeat whereas the MSB sets to 1, so we can compute the MSB bits from 8  11 can as N  2x + 1 = 11  8 + 1 = 4.
Now all that remains is a 3bit range from 8  11 which can now be visualized as 0  3 after removing the MSB, which we can recursively check by changing N to (N  2x).
These observations conclude us to our approach which deals with checking for a complete set before the number and computing its result, later on, computing the MSB bit result from the range 2x to N and then recursively calling the function for the range (N  2x).
Time Complexity: O(logn)
The time complexity for the function is logarithmic which is due tin calculating the largestPowerOfTwo() function.
Space Complexity: O(1)
The space complexity for the function is constant.

Asked in Companies

Related Topics