## Total Number of Set Bits in all numbers from 1 to n

Q. We have to find the total number of set bits in all numbers from 1 to n

## Approach 1 (Brute Force)

We could iterate over all the numbers from 1 to n and count the number of set bits in each number using __builtin_popcount(i) for each i from 1 to n. The time complexity is O (n log n) since we iterate over n numbers and each iteration requires log n time (because the time complexity of __builtin_popcount is log n). Note that there are other similar methods to __builtin_popcount which do the same function in O (log n).

Code In C++ –

Time Complexity = O (n log n)

## Approach 2 (Dynamic Programming)

Let dp[i] denote the number of set bits in the ith number. We will calculate dp[i] in O (1) and thus get an overall time complexity of O(n).

Case 1 (n is even): -

Observe that if n is even then the number of set bits in n is the same as the number of set bits in n/2. For example, if n = 6 = 110 (in base 2) then on dividing by 2 we get n = 11 (in base 2). As a result, only the last non-zero bit is removed and the number of set bits does not change. Thus, in this case dp[n] = dp[n/2].

Case 2 (n is odd): -

If n is odd then the last bit will be set. Thus, we can subtract 1 from n and all the other bits will be the same except the last bit which will be 0. For example, if n = 101001(in base 2) and we subtract 1 then we are left with n = 101000(in base 2) . As a result, we go back to case 1 and our answer is dp[n] = 1+dp[n-1] because there is 1 more set bit in this number than in n-1 and the rest of the bits remain the same.

Thus, we can easily compute the values by simply iterating from 1 to n with the base case that dp = 0.

Now we just need to sum up all the dp values

Code In C++ –

Time Complexity = O(n)

It is highly recommended to solve below problems, they are handpicked by Programmers Army:

Practice Problems :-