HackerRank Probability – Random Integers Random Bits

Challenge: Random Integers Random Bits

Subdomeniu: Probability (probability)

Scor cont: 60.0 / 60

Submission status: Accepted

Submission score: 1.0

Submission ID: 464756904

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/rirb/problem

Cerinta

Given an integer range [A,B],  

1. What’s the probability to get a 1-bit if we first randomly choose a number x in the range and then randomly choose a bit from x?  
2. What’s the expected number of bit 1s if we randomly choose a number x in the range?  

**Input Format**  
The first line of input is the number of test cases $T$  
Each test cases is a line contains 2 integers $A$ and $B$ separated by a space. 

**Output Format**  
For each test case output a line containing 2 float numbers separated by a space. The first one is the probability and the second one is the expected number. You should output the number accurate to 5 fractional digits. 


**Constraints**  
$1 \le T \le 200$  
$1 \le A \le B \le 10^{10}$  

**Sample Input**

	1
	2 4

**Sample Output**
	
    0.61111 1.33333

**Explanation**  
(10)  (11)  (100)  
(1) So we got a one in $\frac{1}{3} \times \frac{1}{2} + \frac{1}{3} \times \frac{1}{1} + \frac{1}{3} \times \frac{1}{3} = \frac{11}{18}$  
(2) The expected 1 we have is : $1 \times \frac{1}{3} + 2 \times \frac{1}{3} + 1 \times \frac{1}{3} = \frac{4}{3}$

Cod sursa

#include <bits/stdc++.h>
using namespace std;

using i128 = __int128_t;
using u128 = __uint128_t;

static inline i128 prefixPopcount(unsigned long long n) {
    // sum_{x=0..n} popcount(x)
    i128 total = 0;
    u128 nn = (u128)n + 1; // count of numbers
    for (int b = 0; b < 64; ++b) {
        u128 half = (u128)1 << b;
        u128 cycle = half << 1;
        if (half > nn && b > 0) {
            // for larger b, term will be 0
            if (((u128)1 << b) > nn && ((u128)1 << (b + 1)) > nn) {
                // keep loop simple; break when half exceeds nn and no remainder can add
            }
        }

        u128 full = nn / cycle;
        u128 rem = nn % cycle;
        u128 ones = full * half + (rem > half ? rem - half : 0);
        total += (i128)ones;

        if (half > nn) break;
    }
    return total;
}

static inline long double prefixRatio(unsigned long long n) {
    // sum_{x=1..n} popcount(x) / bitlen(x)
    if ((long long)n <= 0) return 0.0L;

    long double ans = 0.0L;
    for (int L = 1; L <= 64; ++L) {
        u128 l = (L == 1 ? 1 : ((u128)1 << (L - 1)));
        if (l > (u128)n) break;
        u128 r = ((u128)1 << L) - 1;
        if (r > (u128)n) r = (u128)n;

        unsigned long long ll = (unsigned long long)l;
        unsigned long long rr = (unsigned long long)r;

        i128 ones = prefixPopcount(rr) - prefixPopcount(ll - 1);
        ans += (long double)ones / (long double)L;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    cout.setf(std::ios::fixed);
    cout << setprecision(5);

    while (T--) {
        unsigned long long A, B;
        cin >> A >> B;

        unsigned long long cnt = B - A + 1;

        i128 sumOnes = prefixPopcount(B) - (A == 0 ? 0 : prefixPopcount(A - 1));
        long double expected = (long double)sumOnes / (long double)cnt;

        long double sumRatio = prefixRatio(B) - (A == 0 ? 0.0L : prefixRatio(A - 1));
        long double prob = sumRatio / (long double)cnt;

        cout << (double)prob << ' ' << (double)expected << '\n';
    }

    return 0;
}