1

Possible Duplicate:
Expand a random range from 1-5 to 1-7

Hi, This question is taken from http://blog.seattleinterviewcoach.com/2009/02/140-google-interview-questions.html

Given a function which produces a random integer in the range 1 to 5, write a function which produces a random integer in the range 1 to 7.

I am not getting a way to generate all random numbers 1 to 7 with almost equal probability by using 1 to 5 random generator.

Could anyone pls solve it ?

Community
  • 1
  • 1
bjskishore123
  • 6,144
  • 9
  • 44
  • 66
  • Does the distribution have to be uniform? Do you get a uniform distribution from the provided function? Could you just ignore the provided function? :) – Karl Knechtel Dec 04 '10 at 12:06

2 Answers2

1

I assume that the function you're given provides uniformly distributed-numbers and it is a strict requirement that the function you need to write also returns uniformly-distributed numbers.

The following pseudo-code illustrates the standard technique (called rejection sampling):

do {
  rand25 = (rand5() - 1) * 5 + rand5; // 1-25
} while (rand25 > 21);
return (rand25 - 1) / 3 + 1;
NPE
  • 486,780
  • 108
  • 951
  • 1,012
-1

What about func() + func() % 3 ?

qutron
  • 1,710
  • 4
  • 18
  • 30
  • just noticed, probability must be the same. This solution changes distribution. – qutron Dec 04 '10 at 12:25
  • This is a bad idea as it destroys the distribution properties of `func()`. In `func() % 3` getting a `1` or `2` is twice as likely to get a `0`, assuming `func()` has an equal distribution. – bitmask Aug 18 '12 at 13:59