Count the Ones

 Alice recently converted all the positive integers from 

1$1$ to 2N−1$2^N-1$ (both inclusive) into binary strings and stored them in an array S$S$. Note that the binary strings do not have leading zeroes.
While she was out, Bob sorted all the elements of S$S$ in lexicographical increasing order.

Let Si$S_i$ denotes the ith$i^{th}$ string in the sorted array.
Alice defined a function F$F$ such that F(Si)$F(S_i)$ is equal to the count of 1$1$ in the string Si$S_i$.
For example, F(101)=2$F(101)=2$ and F(1000)=1$F(1000)=1$.

Given a positive integer K$K$, find the value of ∑Ki=1F(Si)$\sum _{i=1}^{K}F(S_i)$.

String P$P$ is lexicographically smaller than string Q$Q$ if one of the following satisfies:

• P$P$ is a prefix of Q$Q$ and P≠Q$P\ne Q$.
• There exists an index i$i$ such that Pi<Qi$P_i<Q_i$ and for all j<i$j<i$, Pj=Qj$P_j=Q_j$.

Input Format

• The first line will contain an integer T$T$ - number of test cases. Then the test cases follow.
• The first and only line of each test case contains two integers N$N$ and K$K$.

Output Format

For each test case, output the value ∑Ki=1F(Si)$\sum _{i=1}^{K}F(S_i)$.

Constraints

• 1≤T≤3000$1\le T\le 3000$
• 1≤N≤50$1\le N\le 50$
• 1≤K≤2N−1$1\le K\le 2^N-1$
• Sum of N$N$ over all test cases does not exceed 105${10}^5$.

Sample Input 1 

3
3 2
3 4
3 7

Sample Output 1 

2
5
12

Explanation

Converting positive integers to Binary Strings:

• 1=1$1=1$
• 2=10$2=10$
• 3=11$3=11$
• 4=100$4=100$
• 5=101$5=101$
• 6=110$6=110$
• 7=111$7=111$

Sorting Binary Strings in lexicographical order: After sorting, the strings will appear in the following order:
[1,10,100,101,11,110,111]$[1,10,100,101,11,110,111]$.

Test case 1$1$: F(S1)+F(S2)=F(1)+F(10)=1+1=2$F(S_1)+F(S_2)=F(1)+F(10)=1+1=2$.

Test case 2$2$: F(S1)+F(S2)+F(S3)+F(S4)=F(1)+F(10)+F(100)+F(101)=1+1+1+2=5

• Tweet
• Share
• Share
• Share
• Share

Related Post