Pepcoder And Bits

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

1. Pepcoder is feeling confident after solving many problems on Bit Manipulation.
2. So, his teacher ask him to find out the count of positive integers strictly less than N, having same
number of set bits as that of N.
3. Let us see that if pepcoder can solve it or not.
Input Format
A number N
Output Format
Check the sample ouput and question video.
Question Video
Constraints
1 <= N <= 10^12
Sample Input
1024
Sample Output
10


  • Editorial

    The problem here deals with getting all the numbers in the range 0 to (n-1) which have the same number of set bits as that of n.

    Say for example n = 12 [ 1 1 0 0 ]

    Output: 5 { 3[ 0 0 1 1 ], 5[ 0 1 0 1 ], 6[ 0 1 1 0 ], 9[1 0 0 1 ], 10[ 1 0 1 0 ] }

    The problem can be solved with the help of recursion. Here we will choose every step that whether to set this bit or not and then we would act accordingly. Suppose we have [ 1 1 0 0 ] then for the first case we would choose that whether we want the MSB to be 1 or 0. If MSB is set to 0 then we have to put two 1s in the remaining three spaces which can be done in 3C2 ways. And if we set MSB to 1 we have to solve recursively for {1 0 0} as we only need to have numbers which are lesser than n so any combination that could be greater than n must be neglected and our recursion ensures that every combination yields number less than n. 

    Thus we can have two cases:

    1. The bit is already set

    This is the case when we have two options, if we choose this bit value is 0 then we will have all numbers less than n irrespective of the combination of latter bits so here we do not recurse but simply calculate the combinations possible. The other case is when we choose to set this bit, in this case, there is a possibility that the combination of latter bits can yield to a number greater than n so we choose to recurse.

    2. The bit is not set

    This is the case when no operations need to be done and we just need to recurse to the next index as setting this bit would yield a number greater than n.Time Complexity: O(n!)

    The time complexity for the recursive call is linear as the recursive function if of the type T(n) = k + T(n - 1) but we have to find nCr for every n which is a costly operation.

    Space Complexity: O(n)

    The space complexity for the function is linear due to the recursive stack.

  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name