The Best Actor
All submissions for this problem are available.
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 all
actors 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)
First line contains T (Number of test cases).
Next T lines contain a single integer N.
For each testcase print the minimum number of expected function calls of random_bit() function required to generate a random number between 1 to N such that every number should be generated with equal probability.
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 100000
Input: 2 2 3 Output: 1.000000 2.666667
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, CS2, GO|
Fetching successful submissions
If you are still having problems, see a sample solution here.