I heard an interesting trick question recently: “Given a function that returns a random integer between 1 and 6, use it to write a function that returns a random integer between 1 and 7.”

I quickly came up with a solution that works, but isn’t optimal in one sense. The idea is to use the given Random16() function to generate three binary 0 or 1s (0 if Random16 is 1, 2, or 3 — 1 if Random16 is 4, 5, 6) then use those to construct a 3-bit number in the range 1-8. If the result is 8, try again, otherwise return the result.

I coded up the algorithm using C# to make sure it worked (it did).

One advantage of my mini-algorithm is that it can be easily adapted to just about any similar problem. A disadvantage is that there’s a very clever way to solve the problem that uses only two calls to Random16() instead of the three calls required by my approach. Interesting problem.

public static int Random16() // given
{
return rnd.Next(1, 7); // [1, 7) = [1, 6]
}
public static int Random17()
{
// use given Random16 to generate a 3-bit number [1,8]
// toss out an 8 result
while (true) // until a valid result
{
int result = 1;
for (int bit = 0; bit < 3; ++bit)
{
int r16 = Random16(); // 1-3 = "0", 4-6 = "1"
if (r16 >= 4) // "1" bit
result += (int)Math.Pow(2, bit);
}
if (result <= 7)
return result;
}
}

### Like this:

Like Loading...

*Related*

Two calls to the given randomizer produces 36 distinct outcomes.

If we consistently discard one outcome, we are left with 35 combinations which can be be thought of as 7 groups of 5.

Determining which group of 5 to index produces the desired random7() function, This is completed with only 2 calls (97% of the time) to random6().

Note, we work zero-relative, to keep the math simple. Here’s the java code:

import java.util.Random;

/* Created by davidqkleinberg on 10/27/16. */

public class McCaffreyRandomizer {

private static Random rand = new Random();

public static void main(String[] args) {

for (int i=0; i ” + random06;

System.out.println(str);

}

}

}

private static int random05(){

return rand.nextInt(6); // 6 possible values, zero relative i.e., 0-5

}

}

Quite right! This is the “clever” technique I was referring to.