Given a random int generator [0-5], generate [0-7]

Question

So this was an interview question.

You are provided with a function rand5() which generates a random integer in the range [0-5] i.e. {0,1,2,3,4,5}

a) Can you use that function to generate a random integer in the range [0-7]?

b) Can you use that function to generate a random integer in the range [0-7] with each number having equal probability?

You may use the function multiple times.

One of the solution for part a, ((rand5() +rand5())*7)//10 where // represents integer division would give you the range [0-7] however the probabilities are not equal.

Would love to see your answers and thought process on this.

Answer 1

    $one  = rand5();
    $two  = rand5();
    $four = rand5();

    return (($four < 3)? 4 : 0)  +  (($two < 3)? 2 : 0)  +  ($one < 3)? 1 : 0);

Answer 2

This can be done using Rejection Sampling.
Consider the rolls arranged in a 2D grid like below

[0, 1, 2, 3, 4, 5]
[0, 1, 2, 3, 4, 5]
[0, 1, 2, 3, 4, 5]
[0, 1, 2, 3, 4, 5]
[0, 1, 2, 3, 4, 5]
[0, 1, 2, 3, 4, 5]

Now if you roll the die twice you can generate any position in the 2D grid (first row for row position, second for column position). There are 36 positions in total. Since we want to generate numbers in [0, 7] range we need output space to be a multiple of 8. If we consider first 32 positions (in a row major order) we can split them into group of 4 indices. For example

[0, 1, 2, 3] in first row => 0
[4, 5, 0, 1] in first and second row => 1
[2, 3, 4, 5] in second row => 2
...
[4, 5, 0, 1] in fifth and sixth row => 7

If we roll last 4 positions, we will just roll again.

int rand7() {
    while(true) {
        int row = rand(5);
        int col = rand(5);
        int pos = row * 6 + col;
        if(pos < 32) {
            return pos/4;
        }
    }
}