Shreyansh and his bits

please can someone help me with this problem about approach how to solve this problem
refer:- https://practice.geeksforgeeks.org/problems/shreyansh-and-his-bits/0

Shreyansh has an integer N. He is really curious about the binary representation of integers. He sees that any given integer has a number of set bits. Now he wants to find out that how many positive integers, strictly less than N, have the same number of set bits as N .
He is a little weak in maths. Help him find the number of integers.
Note : Since N takes large values, brute force won’t work.

Input :
First line of input contains a single integer T denoting the number of test cases.
The only line of each test case contains an integer N.

Output :
For each test case, print the required answer in a new line.

Constraints :
1 <= T <= 1000
1 <= N <= 10^12

Example :
Input :

3
8
1
4

Output :
3
0
2

Explanation :
Case 1 :
Binary representation of 8 : 1000
So the integers less than 8 with same number of set bits are : 4, 2, 1

Case 2 :
Binary representation of 1 : 1
There are no positive integers less than 1.

Case 3 :
Binary representation of 8 : 100
So the integers less than 4 with same number of set bits are : 2, 1
thank you

You don’t need to count numbers.
You just need basic knowledge of permutations and combinations.
For example say: N = 10
10 in binary is 1010:
Possible combinations(Where X<N):
0011
0101
0110
1001

Output: 4

So you need to find total possibilities where you can select any 2 bits such they are on and all other bits are off. Then subtract the combinations that exceed N.

A = All Possible Combinations = {0011,0110,0101,1001,1010,1100}
B = Combinations that exceed OR equal to N = {1010,1100}
Combinations less than N = {0011,0101,0110,1001} = A - B

1 Like

thank you for the help really apperciated.
can please provide a code.
i cannot think of O(n) solution

@hackinet you forgot 0101. The answer to your test case should be 4.

1 Like