Don't practice until you get it right. Practice until you can't get it wrong.
Count Set Bits in First N Natural Numbers
Welcome back, dear reader. So, how is it going? In this article, we will discuss this problem called COUNT SET BITS IN FIRST N NATURAL NUMBERS. So, the objective is clear from the question name only. We have to count the number of set bits of the first N natural numbers. For instance, say n=3. This means that we have to count the number of set bits of the first 3 natural numbers. The natural numbers start from 1. So, the first 3 natural numbers are 1,2, and 3. So, we count the number of set bits in 1 2, and 3 as shown in the image below:
Hope that you have understood the problem. We recommend you try to solve this problem on your own first and then refer to the solution.
Approach :
Time Complexity: O(log2n) where n is the number entered as the input
Space Complexity: O(1)
Algorithm:
Calculate the set bits of the first 2x numbers by using the formula x* 2x-1.
Then, calculate the set MSB's in the remaining numbers i.e. N-2x+1.
Apply the procedure recursively for N-2x elements till n becomes 0.
Explanation:
You can solve this problem by calculating the total number of set bits in each number using Kernighan's algorithm and then adding all these up to N. But, this is not a very efficient or smart way of solving this problem. Still, we recommend you try to code this method too as it will be good for your hands-on practice. Let us now think of an efficient method to solve this problem.
Let us say we have to solve this problem for N=11 i.e. we have to solve this problem for first N natural numbers where N=11. The first N=11 natural numbers are shown below:
The input given to us was eleven. First of all, we will calculate the highest power of 2 in the range. What do we mean by this? See, we are given eleven as the inp0ut. The highest absolute power of 2 which is less than 11 is 8 i.e. 23 as 24 is 16 which is greater than 11.
Why are we finding this? This is because if we know the highest power of 2 in the range, we can calculate the number of set bits before that. Here, the highest power of 2 is 3. So, the number is 23 i.e. 8.
We can very easily calculate all the set bits before 8. The word before is really important as we will be able to calculate the number of set bits from 0 to 7 and not 8.
Now you might be thinking that 0 is not a natural number. So, why are we including it? This is because it does not have any set bits either. So, if we include it too, the answer will not be affected.
Now let us see why we are saying that it is easy to calculate the set bits till the highest power of 2 (excluding it i.e. from 0-7 and not 8 in this case). Have a look at the binary numbers from 0 to 7.
Have a look at the pattern that the bits at position 1 i.e. LSB follows. They are on and off alternatively i.e. the 1st bit is OFF in 0 and then it is ON in 1 then again OFF in 2 and ON in 3 and so on. Now, if we think carefully, we will understand that there are 8 numbers and out of them, 4 are having the 1st bit as ON, and 4 have 1st bit OFF.
So, if the highest power of 2 in the range is x i.e. 3 in this case, the number of set bits at position 1 in the first 2x (=8 in this case) numbers is (2x/2).
Now, let us have a look at the second bit for these numbers i.e. the bit at position 2.
If we look at these bits, they are alternatively OFF and ON in groups of 2 i.e. first two numbers have the bits at the 2nd position as OFF and the next two numbers have these bits ON and so on. So, if we calculate, we again find out that the 4 bits are ON and 4 bits are OFF. Therefore we can say that:
If the highest power of 2 in the range is x, then the number of set bits in the first 2x numbers is (2x/2) at the 2nd position.
Now let us move to the third-bit position.
Here, we have the first 4 bits ON and the rest 4 bits OFF i.e. a total of 2x/2 bits are ON in this case.
If the highest power of 2 in the range is x, then the number of set bits in the first 2x numbers is (2x/2) at the 3rd position.
The bits at the 4th position are all OFF and we can see that. So, we can say that the first, second, and third position bits are having 2x/2 bits on each. So, we can say that a total of 3 x 2x/2 bits are on. Here this 3 is also the value of x and 2x/2 can be written as 2x-1.
So, a total of 2x-1 * x bits are on in the first 2x numbers out of N numbers.
So, let us try to apply this formula to our question where we have to calculate the total number of set bits till N=11.
You can verify this by taking some other input as well. Calculate the highest power of 2 in the range first and apply the same formula to get the set bits in the first 2x numbers.
Now, let us think about the remaining numbers. How many remaining numbers do we have? We had N as the input and we have already calculated the set bits in the first 2x numbers.
N-2x numbers are remaining for which we have to calculate the set bits. If you have a look at the 4thbit of all the remaining numbers, it is set. This means that we have calculated N-2x +1 set bits more in addition to the previous x* 2x-1 set bits.
Since we know that the remaining numbers have only set bits at position 4 and we have already counted them, our question reduces to a smaller size now. We do not need to consider the entire number, rather, we can consider only the bits at positions 2, 3, and 4. So, we now have reduced question:
Now if we look at the diagram above, we can say that we have removed the bits at position 4 from the remaining numbers as we have already counted them. So, if you have a look at the remaining numbers, it appears as if we have subtracted 8 from the numbers as in place of 8, we have 0 and in place of 9 we have 1, and so on. Now, what are these? These are the first 3 natural numbers (0 is not included in natural numbers). So, we can say that our problem has now been reduced to a small problem where we have N-2x natural numbers now.
So, we can solve this using recursion. So, this is how we can solve our problem in a much more efficient way than counting all the set bits for one number and adding them on for all the numbers.
So, finally, if we want to conclude this for our question, we can say that:
So, we have now understood how we can solve this problem in a much faster and efficient way. We recommend you watch the solution video to understand the above procedure completely. Now, let us have a look at one more small thing remaining i.e. calculation of x.
How to get Maximum Power of 2 in Range?
We will start x from 0 in our code. We will check the value of 2x and see whether it is greater than N or not. If it is not greater than N, we will increment N. If the value of (1<< x) which is 2x becomes greater than N, we will return x-1 as this will be the highest power of 2 in range.
For instance, N=11. We start from x=0. Since 20 =1 is less than 11, we increment the value of x i..e. x=1. Again, we will calculate the value of 2x=212 which is still less than N=11, so we will again increment the value of x and x becomes 2. Again, 2x=22 I.e. 4 is less than N=11, so again x will be incremented by 1. Now, 2x = 23 =8 is less than N=11, increment the value of x and x becomes 4. Now, x=4 and 2x =24 =16 is greater than N=11. So, we will stop here.
The value stored in x is 16 right now but it is out of the range. So, we will decrement the value by 1 i.e. x=3 will be the highest power of 2 in the range.
So, this is the procedure for calculation of Maximum Power of 2 in Range.
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
System.out.println(solution(n));
}
public static int solution(int n) {
if (n == 0) {
return 0;
}
int x = largestPowerOf2inrange(n);
int btill2x = x * (1 << (x - 1));
int msb2xton = n - (1 << x) + 1;
int rest = n - (1 << x);
int ans = btill2x + msb2xton + solution(rest);
return ans;
}
public static int largestPowerOf2inrange(int n) {
int x = 0;
while ((1 << x) <= n) {
x++;
}
return x - 1;
}
}
java;
true";
The above code is based on the procedure explained in this article and the solution video. The code is explained in the solution video. You may refer to it if you have any doubts regarding the code. Now that we have understood the complete procedure and code, let us analyze the time and space complexity of the above code.
Analysis
Time Complexity:
Although we are using recursion, the time complexity of this method is almost O(log2n). This is because we are solving a large number of elements just by the formula and we apply the recursion on a very small set of numbers after that. For instance, in our example, we solve 8 out of 11 numbers with a formula and the remaining were only 3 numbers which is approximately O(log2n) and don't forget that when the recursion will be applied to these numbers then again, the problem will be solved using the formula for first 2x elements
Space Complexity:
The space complexity will be O(1) as we have not used any extra space. If we consider the recursive space, the space complexity will be O(h) where h is the height of the recursion tree.
So, dear reader, if you have any doubts regarding the procedure or the code, refer to the complete solution video to clear all your doubts. With this, we have completed this question.
Suggestions:
Here are a few suggestions from our side that you do not want to miss:
We recommend you refer to the solution video (12:49 onwards) to understand the dry run of the code and the procedure for a bigger example.
We also suggest you try to dry run the procedure for a bigger number once. This will be helpful for your conceptual understanding. So, keep practicing and moving forward. Till then, Happy Coding!!!