Challenge – Equal Probability between 1 and 7

Question: Write a method to generate a random number between 1 and 7, given a method that generates a random number between 1 and 5. The distribution between each of the numbers must be uniform.

Challenge: Do you know the answer to this question? Post in the comments. Let’s see who is up for the challenge. Answers will be posted February 26th.

Let’s think of this like a decision tree. Each rand5() will be a decision. After 2 tries, we have 25 possible solutions. We try to get maximum bunches of 7 as we can (1 – 21, 3 sets of 7). If we get any of the other values, we just try again. Since the probability of getting each of 21 values are the same every time, trying again won’t affect their probabilities.

Equal Probability 1 to 7

int rand7() {
    while (1) {
        int num = 5*(rand5()-1) + rand5();
        if (num < 22) return ((num % 7) + 1);
    }
}

That was fun, right? Anyone up for another challenge? Watch out for it next tuesday (March 1st).

If you're looking for some serious preparation for your interviews, I'd recommend this book written by a lead Google interviewer. It has 189 programming questions and solutions:

Book Cover
Button
84 Comments

84 Responses

  1. Ashwin says:

    = rand5()*1 + rand5()*2 + rand5()*4

  2. hocHo says:

    Apologies for the error in the previous post. Should be this…

    Create an array ‘a’ of 5 x 7 = 35 elements and populate it with 5 sets of 1 through 7.

    So we have something like
    1 2 3 4 5
    6 7 1 2 3
    4 5 6 7 1
    2 3 4 5 6
    7 1 2 3 4
    5 6 7 1 2
    3 4 5 6 7

    Hold the state as ‘s’ = 0;

    So for each call the random number would be

    a[((s++ % 7) * 5) + Rand5() – 1]

    If necessary allow ‘s’ to be set initially as a seed value.

  3. Rob says:

    this is easy, generate 7 random numbers between 1-5, add them together and divide by five. Then round that number down and you will get a equally distributed number between 1-7. To further explain
    if you add 7 random numbers between 1-5 you will get a sum of 7 – 35. If you then divide that sum by 5 you will received a result of 1.4 – 7 which when rounded down will give you an equal distribution of numbers between 1-7.

  4. dave says:

    As 7 doesn’t divide 5^k for any integer k, a uniformly selected number between 1 and 7 can not be generated by a finite number of calls to rand_1_5(). However, an algorithm can be constructed so that it will terminate with probability 1.

    A simple solution would be something like

    int rand_1_7() {
    int random;
    do {
    random = (rand_1_5() - 1) * 5 + (rand_1_5() - 1);
    } while (random >= 21);
    return random % 7 + 1;
    }

    If rand_1_5() is a slow function, we can make an effort into not not wasting entropy obtained from it.


    int rand_1_7() {
    int cur = 0;
    int max = 1;
    do {
    do {
    cur = cur * 5 + rand_1_5() - 1;
    max *= 5;
    } while (max < 7);
    if (cur < (max/7)*7) {
    return (cur%7)+1;
    } else {
    cur = cur % 7;
    max = max % 7;
    }
    } while (1);
    }

    It requires slightly fewer calls to rand_1_5() (about 2.21 on average, instead of 2.38).

  5. Satvik says:

    s = rand1to5*5+rand1to5;
    if s < 27 then x = s mod 7;
    else return;

  6. Zephod says:

    I think the simplest solution is to work out a 2-digit number in base 5 (value from 0 to 24). We have three uniform-distribution blocks of seven in that space, and an ugly end-bit. So if the value is in the ugly end bit (21-24) just drop it and try again.

    I haven’t got a formal proof but this should provide a uniform distrubution:

    while (true) {
    int n=(random5() * 5) + random5() – 6; // 0 to 24
    if (n<21) return (n%7) + 1; // 1 to 7
    } // Loop until we hit a good value

  7. Rob Desbois says:

    Is it given that the function returning a random number between 1 and 5 does so with uniform distribution?
    If so then the following works by scaling it up so keeping the given distribution:


    def rand1to7
    return (1.5 * (rand1to5 - 1)) + 1
    end

  8. some_func(){
    tmp = 0
    tmp += random5() foreach 0:7
    return tmp%7
    }

  9. hocho says:

    Create an array ‘a’ of 5 x 7 = 35 elements and populate it with 5 sets of 1 thru 7.

    So we have something like
    1 2 3 4 5
    6 7 1 2 3
    4 5 6 7 1
    2 3 4 5 6
    7 1 2 3 4
    5 6 7 1 2
    3 4 5 6 7

    Hold the state as ‘s’ = 0;

    So for each call the random number would be

    a[(s++ % 7) + Rand5() – 1]

    If necessary allow s to be used as a seed value.

  10. hocho says:

    Create an array ‘a’ of 5 x 7 = 35 elements and populate it with 5 sets of 1 through 7.

    So we have something like
    1 2 3 4 5
    6 7 1 2 3
    4 5 6 7 1
    2 3 4 5 6
    7 1 2 3 4
    5 6 7 1 2
    3 4 5 6 7

    Hold the state as ‘s’ = 0;

    So for each call the random number would be

    a[(s++ % 7) + Rand5() – 1]

    If necessary allow s to be used as a seed value.

  11. Adam says:

    int result;
    do {
    result = 0;
    result += (rand1to5() – 1); // first two bits, uniform
    tmp = 0;
    do {tmp = rand1to5(); } while(tmp == 5); //
    result += (tmp % 2 << 3) + 1;
    } while(result == 8);

  12. WoopAT4 says:

    In the method below, each number competes in a round robin twice. The competing numbers use Rand5 mod 2. Because Rand5 favors the odd number, two loops are performed. The first one favors the inner loop, the second favors the outer loop. Each number will compete 12 times until there is a clear winner.

    Public Function Random7() As Integer
    Dim oRand As New Random()
    Dim iArray(6) As Integer
    Dim iIndex As Integer = -1
    Dim iValue As Integer = -1

    While iIndex = -1
    Array.Clear(iArray, 0, iArray.Length)

    iIndex = -1
    iValue = -1

    For i As Integer = 0 To 5
    For j As Integer = i + 1 To 6
    iArray(IIf(m_oRand.Next(1, 6) Mod 2 = 0, i, j)) += 1
    Next j
    Next i

    For i As Integer = 0 To 5
    For j As Integer = i + 1 To 6
    iArray(IIf(m_oRand.Next(1, 6) Mod 2 = 1, i, j)) += 1
    Next j
    Next i

    For i As Integer = 0 To 6
    If iArray(i) = iValue Then
    iIndex = -1
    ElseIf iArray(i) > iValue Then
    iValue = iArray(i)
    iIndex = i
    End If
    Next i
    End While

    Return iIndex + 1
    End Function

  13. Chris Lamont’s is equivalent to mine.

    Requires about 2.4 evals of random 1..5 to get
    random 1..7. One could get it down to about 2.2 evals by not throwing away the randomness of the generated cases that flunk the filter.

    He posted first, but I wrote mine at work and had to come home to post it, and I didn’t really look hard at any of the other entries before I did. Great minds think alike.

  14. import random

    answerMap = { (1, 1): 1,
    (1, 2): 2,
    (1, 3): 3,
    (1, 4): 4,
    (1, 5): 5,
    (2, 1): 6,
    (2, 2): 7,
    (2, 3): 1,
    (2, 4): 2,
    (2, 5): 3,
    (3, 1): 4,
    (3, 2): 5,
    (3, 3): 6,
    (3, 4): 7,
    (3, 5): 1,
    (4, 1): 2,
    (4, 2): 3,
    (4, 3): 4,
    (4, 4): 5,
    (4, 5): 6,
    (5, 1): 7 }

    def rand15():
    return random.randint(1, 5)

    def rand17():
    global answerMap
    randPair = (rand15(), rand15())
    if answerMap.has_key(randPair):
    return answerMap[randPair]
    else:
    return rand17()

    tallies = [0, 0, 0, 0, 0, 0, 0]
    for i in range(1000000):
    tallies[rand17() – 1] += 1
    print tallies

  15. sparc5 says:

    the issue laid on equal probability distribution between [1..7]. Assuming rand_5() is the function to generate number [1..5] and we repeat this function X times and get a sum value, so the possible sum value will be from X to 5X and it is still a equal distribution, then if the total number of possible values between X and 5X can be divided by 7, then the problem is resovled. So we are just looking at this equation:

    5*X - X + 1 = 7 * y

    it is not difficult to figure out a combination:


    X = 5 ; Y = 3

    so the function is

    function rand_7() {
    return (rand_5() + rand_5() + rand_5() + rand_5() + rand_5() - 2) / 3
    }

  16. Jeremy says:

    Here’s a very unusual one that has very even distribution. I’m warning you, it may make you angry.

    int get1_7()
    {
    static bool first = true;
    static std::vector a;
    if ( first )
    {
    first = false;
    for ( int i = 0; i < 7; ++i )
    a.push_back(i+1);
    for ( int i = 0; i < 7; ++i )
    get1_7();
    }
    int i = get1_5();
    int r = a[i-1];
    a.push_back( r );
    a.erase(a.begin()+i-1);
    return r;
    }

  17. Andrew Baine says:


    def rand7():
    n = sum(value * 5 ** index for (index, value) in enumerate([rand5(), rand5(), rand5(), rand5(), rand5(), rand5()]))
    if n == 0:
    return rand7()
    else:
    return 1 + n % 7

  18. Dave says:

    Since the indentation gets all screwed up, I made it easier to read.


    #define f rand15()
    #define s switch
    #define c case
    #define d default
    #define o rand01()
    #define r return
    #define w while
    int o{s(f){c 1:c 2:r 0;c 3:c 4:r 1;d: r o;}}
    int rand17(){int t=0;do{t=o|o<<1|o<<2;}w(t==0);r t;}

  19. Dave says:

    Wateful, but correct:


    int rand01()
    {
    switch(rand15()) {
    case 1: case 2: return 0 ;
    case 3: case 4: return 1 ;
    default: return rand01() ;
    }
    }

    int rand17()
    {
    int tmp = 0 ;
    do { tmp = rand01() | rand01() << 1 | rand01() << 2 ; } while(tmp == 0) ;
    return tmp ;
    }

  20. Paddy3118 says:

    (The commenting system ate the indentation above, even though it was inside code tags).

  21. Paddy3118 says:

    This gives a good distribution for me (it’s in Python):

    >>> import random
    >>> list5 = range(1,6)
    >>> def rand5(): return random.choice(list5)

    >>> def rand7():
    return (sum(rand5() for x in range(7)) % 7) + 1

    >>> bin = dict((x, 0) for x in range(1,8))
    >>> bin
    {1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0, 7: 0}
    >>> for i in range(700000):
    bin[rand7()] += 1

    >>> bin
    {1: 100282, 2: 100464, 3: 99527, 4: 99995, 5: 99962, 6: 100081, 7: 99689}

    – Paddy.

  22. Greg Johnson says:

    Oops. My previous attempt was in error. 1..4 have probability 4/25 of showing up, 5..5 have probability 3/25 of showing up. My bad. How about
    do {
    int rand_0_24 = (rand5() – 1) + 5 * (rand5() – 1)
    rand7 = 1 + rand_0_24
    while (rand7 > 7)

  23. n.b. the order of 5 mod 7 is 6.

    int rand7()
    {
    int sum, i;
    do
    {
    sum=0;
    for (i=0; i<6; i++)
    sum = 5*sum+(rand5()-1);
    }
    while (sum==0);

    return 1+sum%7;
    }

  24. Greg Johnson says:

    int rand_0_24 = (rand5() – 1) + 5 * (rand5() – 1)
    rand7 = 1 + (rand_0_24) % 7

  25. Zach says:

    @Chris Lomont:

    (rand5() – 1)*6/4 still produces a total range of 5 distinct numbers, it does not generate all 7 numbers in the desired output range.

    @mikeash: I like your rand5() + 5 * (rand5() – 1) solution. At first I didn’t think it was uniform until I looked more closely. The rest is more or less what I did earlier (re-rolling if you get a certain number).

  26. Zach says:

    @Anonymous: rand5() + rand5() is not a uniform distribution from 2 to 10. It’s a triangle distribution.

  27. mikeash says:

    First create an evenly distributed distributed random number from 1-25:

    int rand25(void) {
    return rand5() + 5 * (rand5() - 1);
    }

    Now use it to generate a random number from 1-7. For efficiency, I accept the range 1-21 and divide it by 3 to get 1-7. In the range 22-25, retry:

    int rand7(void) {
    int n = rand25();
    return n <= 21 ? n / 3 : rand7();
    }

  28. Ben says:

    Thanks Doggie! I think it was implied as well, but a lot of people (from looking at previous comments) seem to conflate ‘randomness’ with ‘uniform distribution’.

  29. Chris Lomont says:

    (rand5()-1)*6/4+1 works, except you probably want a random *integer* between 1 and 7. Then roll and discard works perfectly fine, treating rand rolls as base 5 digits:
    do {
    val = 5*(rand5-1)+(rand5-1) // in 0-24 uniformly.
    } while val >20;
    // now in 0-20 uniformly
    return (val%7)+1; //

    Doing this for more digits may lower expected running time, for example using three rolls as three base 5 digits, and converting to base 7, re-rolling on values above the n-digit cutoff.

  30. Bob Jones says:

    int rand7() {
    int bits12 = rand5() & 3;
    int bits34 = rand5() & 3;
    return bits12 + (bits34 << 2);
    }

  31. Anonymous says:

    int rand7() {
    int n;

    /* make a uniform distribution from 2 to 10, shift down to 1 to 9, and chop off the top 2 values by re-rolling if you’re above 7 */
    do {
    n = (rand5() + rand5() – 1);
    } while (n > 7);
    return n;
    }

  32. Doggie says:

    I think the uniform distribution is implied but if it wasn’t clear, I will just add that to the question.

  33. Ben says:

    Since you didn’t specify a uniform distribution requirement in the body of your challenge, you can simply take a random number from [1..5] and return that as your random number between [1..7].

    I’m sure someone’s already said that but I haven’t read the comments, as I’m working the proper answer out myself and don’t want to get spoilt 😛

  34. Zach says:

    Another evenly distributed solution is to just roll the die twice. If you roll 11, 12, 13, or 14 erase the result and roll both times again. Repeat until you get something that is not 11, 12, 13, or 14. Then perform the following mapping:

    15,21,22 -> return 1
    23,24,25 -> return 2
    31,32,33 -> return 3
    34,35,41 -> return 4
    42,43,44 -> return 5
    45,51,52 -> return 6
    53,54,55 -> return 7

  35. dschooh says:

    @Zach My calculator played tricks on me. You are absolutely correct, shame on me.

  36. Zach says:

    @dschooh: 5 and 7 are co-prime. The number of outcomes of rolling a 5 sided die is always a power of 5. In this case, 5^13, which is not divisible by 7. Where are you getting 174,386,161?

  37. Zach says:

    Ok it totally butchered my code sample. Don’t know what that’s about.

    Anyway the idea is this:

    Keep trying this algorithm until the number is from 1 to 7. The algorithm is this:

    1) Keep trying to generate a number that’s either 1 or 2, when you do subtract 1 to get either 0 or 1, and use that as the next “bit” in the bit representation of a number.

    2) Do this 3 times. One for the 0’th (rightmost) bit, one for the first bit, and one for the second bit.

    3) The end result of this is an evenly distributed number from 0 to 7. But the original loop will just try again if you have 0, ending up with a number from 1 to 7.

  38. Zach says:

    No solution that involves addition will work, period. In fact, if you’re combining the results of the rand functions at all the solution is highly suspicious. The reason is that these combinations do not generally maintain an even distribution.

    Take addition for example.

    rand_15() + rand_15().

    This will generate two evenly distributed numbers from 1 to 5, add them together, to generate a “random” number from 2 to 10. But this distribution is nowhere near even. In fact, it’s a triangle distrubtion. There’s only 1 possible way to generate the number 2 (1+1) but there are 5 ways to generate the number 6 (1+5, 5+1, 2+4, 4+2, 3+3).

    So, if you’re proposing addition, throw it out the water because it doesn’t work.

    The only foolproof way I can think of so far to generate an even distribution is this:


    int rand7()
    {
    unsigned result = 0;
    int temp = 0;
    while (result == 0)
    {
    for (int i=0; i 2);

    //Scale it to 0 or 1
    --temp;

    //Set the next bit in the result
    result |= (temp << i);
    }

    //Now that we've set bits 0, 1, and 2, we have a number from 0 to 7
    //We need a number from 1 to 7, but the outer while loop will just try
    //again if we have 0. The end result is a number from 1 to 7
    }
    }

  39. dschooh says:

    Idea: Throw 13 5-sided dices, which will have 174,386,161 possible outcomes, which in turn can be devided by 7 and such can be evenly distributed through 1 to 7.

    randoms = []

    13.times do
    randoms.push(rand(5) + 1)
    end

    result = 0

    randoms.each_with_index do |x, i|
    result += x * (5 ** i)
    end

    puts result % 7 + 1

  40. jphofmann says:

    Sorry, y in the for loop should be defined as 0.1.

  41. jphofmann says:

    My solution generates a float in base five between [0,1), and uses that to calculate the random integer between [1,7]. This should be as random and evenly distributed as the generator of [1,5], but no more.

    float baseFive = 0;

    for(float y = 0; y>0; y = y/10)
    {
    baseFive += rand5() * y;
    }

    float baseTen = fromBaseFive(baseFive);

    return ((int)(7*baseTen)) +1;

  42. trueluk says:

    random1to7=function(){

    return 1+(random1to5()+random1to5()+random1to5()+random1to5()+random1to5()+random1to5()+random1to5())%7
    }

  43. Well the function that returns 1 – 5 by default is returning numbers between 1 and 7, it just will not return 6 and 7.

  44. Chris Smith says:

    Hmm, must the answer be guaranteed to terminate in some definite time bound? Or is it sufficient to terminate with probability 1? If the latter, then the question is not difficult. If the former, I haven’t figured it out yet.

  45. EJ Vincent says:

    My first attempt would look like this:

    int x = 0;
    for(int i = 0; i < 7; ++i)
    x += randombetween1and5();
    return (x mod 7) + 1;

    There is a problem with this approach though. This is not an even distribution. Out of the possible results for x mod 7, 0 through 6, 0 will be a possible result 1 more time than any other value.

  46. Eric oetker says:

    I don’t think the above solutions generate a prob density function that is even across 1-7- in order for it to be truly random each number needs to be equally probable. If you roll the random number generator 6 times (to get a max number that is a multiple of 5 and 7) mod 7 the odds should be evenly distributed rather than favoring some numbers.

  47. Doggie says:

    inclusive

  48. Is the between 1 and 5/7 inclusive or exclusive?

  49. Lenny says:

    3/2 * ( random1_5() – 1 ) + 1

  50. Function RandomBetween1And5() As Integer
    Return (some number)
    End Function

    Function RandomBetween1And7() As Integer
    Return 1 + ((RandomBetween1And5() + RandomBetween1And5()) Mod 6)
    End Function

Leave a Reply

Using Gravatars in the comments - get your own and be recognized!

XHTML: These are some of the tags you can use: <a href=""> <b> <blockquote> <code> <em> <i> <strike> <strong>