Competitive Programming: Count total set bits in all numbers from 1 to N

 Hello everyone ... 

Here we are going to solve a Competitive Programming problem related to Bit Manipulation.

Problem Statement

Find the total count of set bits for all numbers from 1 to N(both inclusive).

Examples

Input: N = 4
Output: 5
Explanation:
For numbers from 1 to 4.
For 1: 0 0 1 = 1 set bits
For 2: 0 1 0 = 1 set bits
For 3: 0 1 1 = 2 set bits
For 4: 1 0 0 = 1 set bits
Therefore, the total set bits is 5.

Constraints

1 ≤ N ≤ 108

Expectations

Expected Time Complexity: O(logN)
Expected Space Complexity: O(1)

Problem Link: https://practice.geeksforgeeks.org/problems/count-total-set-bits-1587115620/1

Solution

Approach 

C++ Code

Time Complexity

Since we are only iterating through the bits of N in its binary representation, this solution's time complexity is O(LogN). 

Space Complexity

Since we are using constant space, this solution's space complexity is O(1).

Hooray! We successfully solved this problem with the expected time and space complexity.

Hopefully, you enjoyed this blog post and learned something new. If you want to share anything or if you have any doubts or suggestions please comment below. 

To test how much you understood this solution, I would like to ask one question. 

Question: How to count the total set bits in all numbers from L to R (inclusively), Where L and R are positive Integers and L<=R?

Let me know your answer in the comment section below.

Thank you, guys. 

Have a nice day and stay tuned for new blog posts. Bye ...👋