0

I have been asked this question recently in an interview:

You are given an fair Randon5() function, which return numbers between 1-5 with same probability. Now you need to write a fair Random7() function using Random5() which will return numbers between 1-7, nothing else to use.

Thanks in Advance.

YoungHobbit
  • 13,254
  • 9
  • 50
  • 73

1 Answers1

2

In general it is impossible to do this in bounded finite time, because 7 is not a power of 5. You can do it such that the probability that the procedure runs forever is 0 though, i.e. it will terminate but it's just a question of when.

For one way to do that, run the 1-5 generator twice to get a random number between 1 and 25. If the number is greater than 21, then repeat. Otherwise, if you get a number between 1 and 21, take the remainder when you divide by 7 and add 1. Since 7 divides 21, this will give you a uniform random number between 1 and 7.

Each time you attempt to get a number between 1 and 21, you only have a 4/25 chance that you will fail. Thus the expected number of times you have to iterate the procedure before you succeed is less than 2.

user2566092
  • 4,631
  • 15
  • 20