An infinite stream of numbers is passing through. Write a code which will select a random number out of it at any given time.
SOLUTION
int select_random(){
int n, our_num
int k=1;
scanf("%d", &n);
our_num=n;
while ( scanf("%d", &n) != 0 ){
float rand = random b/w 0 and 1;
our_num = rand < (float)(1/++k) ? n : our_num;
}
return our_num;
}
Subscribe to:
Post Comments (Atom)
2 comments:
could u plz explain the logic........
On arrival of 1st number..select it
On arrival of 2nd number.. u have to select b/w this and chosen one with probability=1/2. hence generate a number b/w 0 and 1. if it is less than 1/2 select 2nd one otherwise, 1st one.
On arrival of 3rd number, chosen one is winner among 2 numbers, so probability of selecting chosen one should be 2/3 and new one is 1/3.
Similarly , on arrival of nth number, select it by probability 1/n and chosen one by (n-1)/n.
Post a Comment