Count the Ones Codechef Solution | MARCH CHALLENGE

Count the Ones Codechef Solution

Alice recently converted all the positive integers from 11 to 2N−12N−1 (both inclusive) into binary strings and stored them in an array SS. 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 SiSi denotes the ithith string in the sorted array.
Alice defined a function FF such that F(Si)F(Si) is equal to the count of 11 in the string SiSi.
For example, F(101)=2F(101)=2 and F(1000)=1F(1000)=1.

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

String PP is lexicographically smaller than string QQ if one of the following satisfies:

- PP is a prefix of QQ and P≠QP≠Q.

- There exists an index ii such that Pi