Welcome back, dear reader. So, how is it going? We hope that you are enjoying your coding journey so far. So, let us discuss this problem called PEPCODER AND BITS. So, what does this question say? We will be given a number N. We have to print the number of all the numbers less than N who have the equal number of set bits as N. For instance if N=12 then its binary equivalent is 1100. So, 5 numbers have 2 set bits. So, the answer will be 5.
The numbers 3,5,6,9 and 10 have also exactly 2 bits set. Therefore, the answer is 5. We hope that you have understood the question completely. If you have any doubts regarding the question above, refer to the solution video to understand the question completely. We recommend you try to solve the problem by yourself first and then refer to the solution.
Approach :
Algorithm:
We will solve this problem by recursion. We will see whether the first bit is set or not. If the first bit is not set, we will simply move to the next bit.
If the first bit is set, we can have two options. The first option is to make the MSB=0 and then from the remaining number, form the numbers which have the same number of set bits. There is no need to worry that the number should be less than the input number s by making the MSB=0, we have ensured that the number we generate will automatically be smaller than the input number.
The second way is to keep the MSB as it is and apply the same procedure recursively for the remaining number.
The base case is when we reach a number for which we cannot have smaller numbers than it having the same number of set bits.
Explanation:
Let us take the number 12. The binary equivalent of 12 is 1100. So, we have to generate the numbers that are smaller than 12 and have the same number of set bits as 2 i.e. 2 set bits. Try to think of some recursive solution to this problem. Did you get any ideas in your mind? Don't worry if you haven't and give a pat on your back if you have. Let's see what we can do about this.
Have a look at the image shown below:
The binary number 1100 (12 in decimal) is taken as the input. Now, we want to get all the numbers that are smaller than 1100 and have the same number of set bits as 1100. So, there are two ways to do that. The first way is that we keep the MSB of 1100 set to 1 only. So, out of 2 bits, we have already set a bit. So, now we have to set only one bit out of the remaining three bits. The other way is that we first ensure that the number that we get is smaller than the input number. So, we make the first bit as 0 i.e. make MSB=0 so that we can ensure that the number that we will get will be smaller than the input given to us. Now that we have ensured this, we have changed the first bit from 1 to 0. So, in the remaining bits, we should now have 2 set bits. The number of bits remaining is 3 (leaving the MSB as it was fixed to 0) and we have to set 2 bits out of it. So, the number of ways in which we can do this is 3C2.
Ok, so we can arrange the two set bits and one 0 bit in 3C2 ways as follows:
What about the first way? Well, if we see, we can apply this method recursively on the remaining number i.e. we have set the first bit to 1 already. After this, the remaining number is 100. The number 100 also has the first-bit set. We will apply the procedure above on this number, that is we will try to generate all the numbers smaller than 100 that have the same number of set bits (i.e. 1) as 100. Why are we trying to do this?
See, we have to generate numbers that are smaller than the input number 1100 and contain the same number of set bits. We have two ways to do that. The first way ensures that the number is smaller than the input number 1100 by keeping the MSB as 0. Since we have changed the MSB from 0 to 1, we have reduced the number of set bits by one in the complete number. So, the remaining places (leaving the MSB as it is set to 0) must have the set bits that were in the remaining number i.e.1000 had one set bit so the remaining places in our number should also have one set bit plus one set bit as we changed the MSB from set bit to 0.
The other way to solve this problem is that we do not change the MSB first. So, MSB=1. Now the remaining places should have the same number of set bits as that in the remaining number. So, the remaining number is 100 i.e. the remaining three places should have one set bit.
Now, we have not taken any measure till now to make the numbers we generate smaller than the given number 1100 as we have already set the MSB to 1. So, the only way to do it is to generate all the numbers with the same number of set bits as 100 which are smaller than 100. So, this is a recursive problem.
So, let us solve this problem recursively. Now we have to generate all the numbers which are smaller than 100 and have the same number of set bits as 100. Now again we have two options. One is to keep the first bit set to 1 and apply the procedure recursively on the remaining number and the other option is to keep the MSB as 0 and generate all the numbers with the same number of set bits.
Now, again we have to apply the procedure recursively on the number 00. Here we have to generate a number smaller than 00 with 0 number of set bits. This is not possible. So, this will act as a base case for recursion. So, we have generated all the numbers that are smaller than 1100 and have 2 set bits. These are 0110, 0101, 0011, 1001, and 1010. So, our answer will be 5 as there are a total of 5 numbers that are less than 1100 and have the same number of set bits as it has.
We request you refer to the solution video to understand the above procedure with the same and a lot more examples to make your concept crystal clear. Let us talk about the base case also.
Base Case
We have talked about the base case in our example when we reached 00. This was a situation when we used to return from recursion as we have to find a number smaller than 00 with 0 set bits. So, what exactly is the base case? Coming of 00 is not a base case. The base case is when we get a number such that we cannot find any number smaller than that number with the same number of set bits as the given number. For example: let us take the input as 1001011. The diagram below shows the application of the recursive procedure.
Here, we have a situation when we reach at 11. We have to generate all the numbers that are smaller than 11 and have the same number of set bits as 11. Since there is no number smaller than 11 with 2 set bits, we have to return from the recursion in this case.
So, whenever we reach a situation where we cannot generate a smaller number with the same number of set bits, that will be our base case.
So, dear reader, we hope that you have understood the above procedure completely. If you have any doubts about it, refer to the solution video to understand till here completely. Now that we have understood everything, let's have an overview of the code first.
Overview of the Code
Before we directly jump into the code let us have an overview of the procedure that we will follow to code here.
First of all, we will make a function to count the number of set bits using Kernighan's algorithm. We need to count the number of set bits of the number to know how many set bits are there in our number.
We will pass three parameters to the solution function. One will be the input number, the second will be the number of set bits and the last will be the index on which we are currently working. We have passed 63 (look at the main function of the code below) because there are 64 bits in the long integer. To understand this, refer to the solution video.
After this, we will apply the above procedure. If the ith bit that we are at is a set bit, we can apply the recursive procedure as told above and if it is not the case, we can count nCr ways. So, we will have to write a separate function for it as well.
Now that you have the overview of the code and what we have to do in it, let us write the code.
import java.io.*;
import java.util.*;
public class Main {
public static long ncr(long n, long r){
if(n < r){
return 0L;
}
long res = 1L;
for(long i = 0L; i < r; i++){
res = res * (n - i);
res = res / (i + 1);
}
return res;
}
public static long solution(long n, int k, int i) {
if(i == 0){
return 0;
}
long mask = 1L << i;
long res = 0;
if((n & mask) == 0){
res = solution(n, k, i - 1);
} else {
long res1 = solution(n, k - 1, i - 1);
long res0 = ncr(i, k);
res = res1 + res0;
}
return res;
}
public static int csb(long n){
int res = 0;
while(n > 0){
long rsb = n & -n;
n -= rsb;
res++;
}
return res;
}
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
long n = scn.nextLong();
int k = csb(n);
System.out.println(solution(n, k, 63));
}
}
java;
true";
We recommend you refer to the solution video to understand the above code and its explanation in depth. Now that we have discussed everything, let's analyze the time and space complexity.
Analysis
Time Complexity:
O(log(N)) where N represent the given number.
Space Complexity:
O(log(N)) where N represent the given number.
So, dear reader, we hope that you have understood the complete procedure. If you still have any doubts regarding anything, refer to the complete solution video to clear all your doubts. With this, we have completed this problem.
Here are some suggestions from our side that you do not want to miss:
We highly recommend you watch the complete solution video once as we have discussed a lot of examples in that video which will cover all your doubts and even the corner test cases will be covered which probably you have not thought about that much.
We also recommend you watch Kerningham's Algorithm Video to understand how we have counted the set bits in the input number if you do not know this algorithm till now. So, keep practicing and moving forward. Till then, Happy Coding!!!
