Write a function which produces a random integer in the range 1 to 7 based on function which returns random integer in the range 1 to 5

The task is given a function rand5() which produces a random integer in the range 1 to 5, write a function rand7() which produces a random integer in the range 1 to 7. The random numbers should be distributed uniformely in the range.

Possible solution:

There are number of possible solutions, I particulary like the one which deals with randon bit generation. Idea behind this solution is to generate bits in the number randomly based on rand5() function.

i.e. 1=0x00000001 and 7 = 0x00000111

So you need populat three first bits of the number with either 1 or 0 and based on the rand5() we can think of following uniform distribution:

n=rand5();

if n>3 then choose 0;
if n<3 then choose 1;
or try again in case n is equal to 3;

Here is sample C# solution:

static int rand7()
{
int sum=0;

while (sum == 0)
{
for (int i = 0; i < 3; )
{
int rand = rand5()

if (rand > 3) sum += (int)Math.Pow(2, i);
else
if (rand == 3) continue;

i++;
}
}

return sum;
}



Company where asked this question: Google, Microsoft