__Total Number of Set Bits in all numbers from 1 to n__

__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] = 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 :-__

• https://leetcode.com/problems/counting-bits/

This article is contributed by Adarsh Agrawal

So that’s it for this article we will be coming up with our next article on further topics of Algorithms very soon till then keep learning, keep coding, keep reading and keep improving !!

**Happy Coding **

**By Programmers Army **
**😊**