Count the Ones Solution Codechef

Count the Ones Solution Codechef

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

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

Given a positive integer K, find the value of ∑Ki=1F(Si)∑i=1KF(Si).

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

• P is a prefix of Q and P≠Q.
• There exists an index ii such that Pi<Qi and for all j<i, Pj=Qj.

Input Format

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

Output Format

For each test case, output the value ∑Ki=1F(Si)∑i=1KF(Si).

Constraints

• 1≤T≤3000
• 1≤N≤50
• 1≤K≤2N−1
• Sum of N over all test cases does not exceed 105.

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
• 2=10
• 3=11
• 4=100
• 5=101
• 6=110
• 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].

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

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

SOLUTION

Program: Count the Ones Solution Codechef in Python

def value(N,k):
    if k==1:
        return 1
    elif k<=2**(N-1):
        return value(N-1,k-1)
    else:
        return value(N-1,k-2**(N-1))+1
def sumk(N,k):
    if k==1:
        return 1
    elif k<=2**(N-1):
        return 1+sumk(N-1,k-1)
    else:
        return 1+(N-1)*2**(N-2)+(k-2**(N-1))+ sumk(N-1,k-2**(N-1))
        
    # Count A_n = 2^N-1
    # Sum A_n = N * 2^(n-1)
T= int(input())
for i in range(T):
    N,K= map(int, input().split(' '))
    print(sumk(N,K))

Program: Count the Ones Solution Codechef in C++

#include <bits/stdc++.h>
using namespace std;
long long ans;
long long calc(int pos, long long k) {
    if(k == 0) return ans;
    ans ++;
    if(k >= (1ll << (pos - 1))) {
        k -= (1ll << (pos - 1));
        ans += (pos - 1) * (1ll << (pos - 2)) + k;
    }
    else k --;
    return calc(pos - 1, k);
}
int main() {
    int tcase, n;
    long long k;
    scanf("%d", &tcase);
    while(tcase --) {
        scanf("%d%lld", &n, &k);
        ans = 0;
        printf("%lld\n", calc(n, k));
    }
    return 0;
}

Codechef March Long Challenge 2022 Solutions

• Bath in Winters Solution Codechef
• Discus Throw Solution Codechef
• Count the Ones Solution Codechef
• MEX on Trees Solution Codechef
• Subarray XOR Solution Codechef
• Substring of a Substring Solution Codechef
• Exact Marks Solution Codechef
• Akash and Function Solution Codechef
• Akash and Missing Class Solution Codechef
• Wordle Solution Codechef