Problem: The Oscar Committee wants to decide which person should get the best actor award among the given N actors.For that they decided to use a random function random_bit() which returns either 0 or 1 with equal probablity. For the results to be fair,the committee was asked to generate a random number between 1 to N (inclusive) , such that allactors have equal probability of being chosen (which in this case should always be equal to 1/N.First of all Committee wants to know the expected number of times they will need to call random_bit() function to generate a random number between 1 to N.Also, while calling the function, they should follow the optimal strategy (i.e. the strategy that minimizes the expected number of function calls)This is problem of  past contests at codechef.com and here's the link to it.This site allows to see other users solution and till now only one solution has been accepted. The solution is in C++ code:#include <iostream>using namespace stdint main() {    int T;    cin >> T;    for(int ii = 0; ii<T; ++ii)     {         int N;         cin >> N;         double p = 1, ans = 0;         int x = 1 % N;         for(int i = 0; i<100000; ++i)         {              ans += x * p;              x = (x * 2) % N;              p /= 2;         }         cout << ans;    }    return 0;}I know how the code runs and what it does, but I can't find the logic behind it. Any help/ clue?Also it would be nice if someone can post another algorithm.
Estimed number of tries
c++;algorithms;problem solving