Time Complexity: O(log₂n) where n is the number entered as the input

Space Complexity: O(1)

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. 2³ as 2⁴ 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 2³ 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 1^st 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 1^st bit as ON, and 4 have 1^st 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 2^nd 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 2^x numbers is (2^x/2) at the 2^nd 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 2^x numbers is (2^x/2) at the 3^rd position.

The bits at the 4^th position are all OFF and we can see that. So, we can say that the first, second, and third position bits are having 2^x/2 bits on each. So, we can say that a total of 3 x 2^x/2 bits are on. Here this 3 is also the value of x and 2^x/2 can be written as 2^x-1.

So, a total of 2^x-1 * x bits are on in the first 2^x 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 2^x 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 2^x numbers.

N-2^x numbers are remaining for which we have to calculate the set bits. If you have a look at the 4^thbit of all the remaining numbers, it is set. This means that we have calculated N-2^x +1 set bits more in addition to the previous x* 2^x-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-2^x 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.

We will start x from 0 in our code. We will check the value of 2^x 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 2^x 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 2⁰ =1 is less than 11, we increment the value of x i..e. x=1. Again, we will calculate the value of 2^x=2¹2 which is still less than N=11, so we will again increment the value of x and x becomes 2. Again, 2^x=2² I.e. 4 is less than N=11, so again x will be incremented by 1. Now, 2^x = 2³ =8 is less than N=11, increment the value of x and x becomes 4. Now, x=4 and 2^x =2⁴ =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.