Count Set Bits In First N Natural Numbers

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

1. You are given a number n.
2. You have to print the count of set bits of first n natural numbers.
Input Format
A number n
Output Format
A number
Question Video
Constraints
1 <= n <= 10^9
Sample Input
17
Sample 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 3-bit 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 = 23-1 * 3 = 2x-1 * 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 3-bits, 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 3-bit 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






Video Solution

Code Solution

Run
 
Run
Id Name