Generate integer from 1 to 7 with equal probability

Generate integer from 1 to 7 with equal probability?

Given a function foo() that returns integers from 1 to 5 with equal probability, write a function that returns integers from 1 to 7 with equal probability using foo() only. Minimize the number of calls to foo() method. 

Sol:

We can generate from 1 to 21 with equal probability using the following expression.

 5*foo() + foo() -5 

Let us see how above expression can be used.
1. For each value of first foo(), there can be 5 possible combinations for values of second foo(). So, there are total 25 combinations possible.
2. The range of values returned by the above equation is 1 to 25, each integer occurring exactly once.
3. If the value of the equation comes out to be less than 22, return modulo division by 7 followed by adding 1. Else, again call the method recursively. The probability of returning each integer thus becomes 1/7.

// Returns 1 to 7 with equal probability 

public static int getRandom()   

{  

    int i;  

    i = 5*foo() + foo() - 5;  

    if (i < 22)  

        return i%7 + 1;  

    return getRandom();  

}