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).

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.