Shreyansh and his bits

please can someone help me with this problem about approach how to solve this problem

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 :


Output :

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):

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