Here is an extension:
Given a pseudo-random generator f() which return unsigned integers
uniformly distributed over the range 0..2^32-1, create a generator
which produces integer values in the range 0..N-1 with each occurring
with a probability {p0, p1, p2, ..., pn-1} such that all the
probabilities sum to 1. Initialization of the generator may require
time O(n) and the generator may require memory of O(n), but generation
of each output must be constant time (O(1)).
DonOn Sep 12, 9:55 am, JITESH KUMAR <jkhas...@gmail.com> wrote: > Hi > You are given a function f() that returns either 0 or 1 with equal > probability. > Write a function g() using f() that return 0 with probability p (where 0<p<1 > ) > > -- > *Regards > Jitesh Kumar* -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
