On Mar 17, 10:24 am, saurabh agrawal <[email protected]> wrote:
> Given a function which returns true 60% time and false 40% time.
>
> Using this function you have to write a function which returns true 50% of
> the time.
If we call the function N times, then the probability that we'll have
K true values returned is binomially distributed: B(N, K; 0.6).
So we can get exactly 50% with N=4. Here we have B(4, 2; 0.6) = B(4,
3; 0.6) = 216/625. So after 4 calls, if we have 2 trues, return true;
if we have 3 trues, return false; otherwise try again with 4 new
calls:
int fair_coin_toss()
{
int i, n;
while (1) {
for (i = n = 0; i < 4; i++) n += unfair_coin_toss();
if (n == 2) return 1;
if (n == 3) return 0;
}
}
The down side of the approach is that we are going to waste 1 -
2(216/625) = 193/625 = ~1/3 of the calls.
Another idea is to again count the number K of trues out of N calls
and return true if K is even, else false. Here the probability of a
true return approaches 50% as N gets larger. For example, with N=9,
it's only off by
1/3906250, which is good for single precision floating point.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
