CareerCup

This is a trick question and there is no correct solution. There are only solutions which are close to correct. The reason for this is that 5 and 7 are relatively prime (also called coprime), so no mapping between them is possible. This means that any solution either (a) does not have the correct probability, or (b) has the possibility of never terminating. All of the solutions given above are therefore incorrect. Lest you think that you can simply convert to binary and back, note that 2 is also relatively prime to both 5 and 7.

I was once asked this question in a phone interview and I tried to explain to the questioner why it was an invalid question, but he didn't understand what "relatively prime" meant.

http://mathworld.wolfram.com/RelativelyPrime.html
http://en.wikipedia.org/wiki/Coprime

Throw the dice 5 times. Calculated the sum of all the throws. The sum will be in the range [5, 25], i.e. 21 different results. For the different results do the following

Result 7-side simulation result
------ ------------------------
5,6,7 1
8,9,10 2
11,12,13 3
14,15,16 4
17,18,19 5
20,21,22 6
23,24,25 7

This solution is inspired from Nanmaga...
Throw the dice twice and do the following:

function rand7() {
throw the dice twice and perform the following checks

1,1 return 1
1,2 return 2
1,3 return 3
1,4 return 4
1,5 return 5
2,1 return 6
2,2 return 7
2,3 return 1
2,4 return 2
2,5 return 3
3,1 return 4
...
...
...
5,1 return 7 [at this point we have returned numbers from 1 to 7, 3 times each]
5,2 rand7()
5,3 rand7()
5,4 rand7()
5,5 rand7()
}

In short, in the last 4 cases, we are subdividing the remaining probability into equal proportions by calling rand7() again.

Any idea if this solution sounds okay?

common solution I saw in some other post:

look at the end bits of the numbers generated by 5:
000
001
010
011
100
101

the lsb is generated wth equal probablity ... hence .. all we need to do is call rand5() 3 times and keep on appending the results to a variable num .. to get our value between 0 and 7

int dice7() {
while (true) {
int num = 5 * (dice5() - 1) + (dice5() - 1);
if (num < 21) return (num % 7 + 1);
}
}

Could you please explain this a bit?..I mean i can throw the die only once per turn?

I mean what is the expected behavior?

the idea here: all sides of the die just should have similar probability to appear:

we throwing 7 times (for each side of 7-sided die) five-sided die and remember sides which got 5, i.e. "qualified" to next round. Then continue until single side left, i.e. got number from 7-side die. (If none got "5" we can either repeat or "qualify" those with "4" and so on).

guys its simple... let me reframe the question in a different way-
write the code for rand7() (that will generate random nos from 0 to 6 each with equal probability) given a function for rand5().

Ans:

rand7()
{
return (rand5() + (rand5()%3));
}

is it that simple?

1. Generate random bits, by calling rand5 until we get something other than 5
2. Output the value mod 2.
3. For generating rand7, call steps 1 and 2 three times, so that you get three random bits and treat them as three-bit binary numbers(range 0..7).
4. Do step 3 until you dont get a 0, then output the value.

Let's say that 5 sided die generates numbers from 0 to 4.
Then throw the die for 7 times and get the total value of each die.
We will get one of 0, 1, 2, 3, ..., 28.
The permutation of 0 happen is 1.
The permutation of 1 happen is 7.
....
The permutation of 27 happen is 7.
The permutation of 28 happen is 1.
(Symmetric)

Get to total value of all the permutations and devide by 7.
Let's say the value from above is V.
Get 7 combination to get V.
Each of 0 to 28 must be used, no duplicat but number of numbers does not matter.
We get unviased 7-sided die.

It can be done in two throws:
Roll the die twice: and simply take XOR of result1 and ~result2.
Explanation:
from 1-5 the three bits have certain probability for 1 on them. By taking 1's complement of the second throw, u find make the probability same for 1 and 0 on each bit. So, 1-7 has same probability.

Throw the dice seven times, number each trial from one to seven, and pick the one with maximum number face-up.
If there is a tie, throw tied ones again to break the tie.
Since all dice are identical, the outputs are distributed uniformly from 1 to 7.
I think andy78 means the same thing bus hasn't explained well.
Even algooz's answer looks good.

hi,guys,the followings are the correct solutions.
Throw the dice5 for 7 times, and sum the number we get. The sum will be a number between 7 and 35, with the same probility. Then, get the modul of the sum devided by 7, which is a number from 0 to 6. Just plus 1, we can get a dice7.

Call the function that generates the random numbers between 1 to 5 twice and add these two results and return modulo 7 of the sum.

int rand7()
{
int i, sum;

for(i = 0, sum = 0; i < 5; ++i)
sum += rand5();

/* sum is in [5, 25] now, but that is not
* a uniform distribution, so subtract 2
* to put it in [3, 23] so that division by
* 3 gives us a nice even [1, 7].
*/

return (sum - 2) / 3;
}

what if I take modulus of rand5() function?
-mod[rand5()*7]

r1=ran15
r2=ran15
r3=ran15
r4=ran15

ranum=(r1+10*r2+100*r3+1000*r4) - 1111

return(Floor(ranum/635)+1)

Explanation:
number of possible values is 4444-0+1=4445. 4445/635 =7
we'll have a range of [0,4444]
min is 0+1=1
max is 4444/635=6.999=6+1=7

I gave same answer as uday (after a lot f confusion) not as easy as it seem but i think: return (rand5()+ rand5()+...7 times) % 7 is OK (truely random)

as far as Tuatha's explanation .. hopefully it's doesn't need to be that complex, i can't imaging coming up with that stuff while on a phone interview.

Heres another scheme -
(rand5-1)*6/4 + 1

explanation:
subtracting by 1 gives a random# between 0 & 4. Dividing by 4 gives a random# between 0 & 1. Multiplying by 6 gives a random number between 0 & 6. Adding 1 to this gives a random number between 1 & 7.

How come summation become uniform distribution? It is becoming Welghted..
I think we can improve the range with complete uniform solution... But we can use rejection... for example:

How come summation become uniform distribution? It is becoming Welghted..
I think we can improve the range with complete uniform solution... But we can use rejection... for example:
---------
int rand7(){
int x = 21;
while( x > 20){
x = 5*(rand5()-1) + (rand5()-1);
}
int r = 1 + (x % 7);
return r;
}
---------
we can improve it if we take to 1-125 range...

Hey, what about using shifting ?
function rndBit()
{
// equal prob. of 0 or 1
return rand5() & 1;
}

rand7= 1+ (rndBit()<<3 | rndBit()<<2 | rndBit()<<1 | rndBit()) & 6;

would not this give us random bits (not weighted) and work ?

I couldn't find an answer myself. :(

int evenrand()
{
return (rand()%4)*2;
}
rand()
{
//returns no between 1 to 5
}

The point of the question is equal distribution. Think about two dimension array (rand(), rand()). This will generate total 25 cases: (1,1), (1,2), ..., (5,5).

In case of (1,1) return 1.
In case of (1,2) return 2.
In case of (1,3) return 3.
In case of (1,4) return 4.
In case of (1,5) return 5.
In case of (2,1) return 6.
In case of (2,2) return 7.
In case of (2,3), in this case, return 1.
Then (2,4) returns 2. And make it recursively until you hit the (5,1). In case of (5,2), (5,3), (5,4) and (5,5) run this logic again. In this way, we can obtain equal distribution.

If the uniformity of numbers among random numbers from 1 to 7 is the most important.

Clacualte:
factor = GCD( <1st_Number>, <2nd_Number> )
iff ( GCD is same as { <1st_Number> or <2nd_Number> )
lcmNo = LCM( <1st_Number>, <2nd_Number> )
factor = lcmNo
Generate 1....factor random numbers of range <1...1stnumber>
Sum them and take modulo of <2nd_Number>

int rand7(){
int random7= 0;
for(int i =0;i<7;i++){
random7 += rand5();
}
return (random7%7);
}

algooz is absolutely correct... his solution is perfect...!!!!

I believe acoder's solution is correct. It will help if someone can argue against it.

Why not something like this:

1) From R5(), we can generate R2() with uniform distribution. How?...
1-ret 1
2-ret 1
3 ret 2
4 ret 2
5 repeat R2()

Modification of this would be

R34()
1-ret 3
2-ret 3
3-ret 4
4-ret 4
5-repeat R34()

Similarly for 5,6 with R56()

Now, to simulate R7(),

1-ret R12()
2-ret R34()
3-ret R56()
4-ret 7
5-repeat R7()

This should be uniformly distributed....anybody thinks otherwise?

do rand5()+rand5()
2(1,1) 3(1,2) 3(2,1) 4(1,3) 4(2,2) 4(3,1) 5 5 5 5 6 6 6 6 6 7 7 7 7 8 8 8 9 9 10(5,5)

if
1,1 = return 1
1,2 = return 2
2,1 = return 3
1,3 = return 4
2,2 = return 5
3,1 = return 6
5,5 = return 7

For all other combinations repeat rolling the dies till one of the above combinations come.

Probability calculation:-
Selection probability for the above case = 1/25.
Rejection probability = 18/25

1/25 + (18/25)*1/25 + (18/25)^2*1/25 + ....

1/25*(18/25 + (18/25)^2 + (18/25)^3 +....)

1/25*(25/7)
= 1/7

Comments/criticisms welcome.

Since this thread is very long, i apologize if some1 has already posted this solution.

Thanks,
Rohith Menon.

Easy:
rand7 = ((ran5 + rand5 + rand5 + rand5 + rand5 - 5) % 7) + 1

The 5 rand will give range 5-25 : 21 numbers.

Equal probability for all.

The solution from lensbo would seem to work if you throw the 5-sided die 14 times. The sum of the die throws will get you a number from 14 to 70 where the range is 56 (a multiple of 7). Take the sum modulo 7, and you get a number from 0 to 6 evenly distributed. Add 1, and you have a 7-sided die.

function rand7() {
v3 = 7;
while (v3 > 6) {
v1 = 4;
while (v1 > 3) {
v1 = rand5();
}
v2 = 4;
while (v2 > 3) {
v2 = rand5();
}
v3 = (v2 << 2) | v1;
}
return v3;
}

why not just sum the result of two rolls, and if it is bigger then 6 try again?

function rand7(){
X1=rand5();
X2=rand5();
X3=x1+x2;
If result>6 return rand7(); // try again
return result;
}

why not just sum the result of two rolls, and if it is bigger then 6 try again?

function rand7(){
X1=rand5();
X2=rand5();
X3=x1+x2;
If result>6 return rand7(); // try again
return result;
}

suppose rand5() returns any number in {1, 2, 3, 4, 5}.

int rand7(){
int X1=rand5();
int X2=rand5();
int result = X1 + X2; //If rand5() returns {0, 1, 2, 3, 4} then {0, 3, 4} must be excluded.
If result >= 8 return rand7(); // try again
return result;
}

i think we can follow this approach:

basically we need three diff bits to mkae those (8) numbers then we could discard 000 from there.
so what we need is a routine whcih generates 0 and 1 with equal probability
int rand2()
{
while(1)
{
int randomNum = rand5();
return randomNum%2; // (equal numer of cases of 1 and 0)
}
}

Main routine to generate 8 randomnumbers btwn (0to 7)

int rand7(

int bit1 = rand2();
int bit2 = rand2();
int bit3 =rand2();
int finalNum = bit1<<2 | bit2<<1 | bit3
if(finalNum! =8)
return finalNum;
}

This will guarantee equal probabilitu for all (0 to 7)

your views?

surprised no one has found the "correct"/optimal answer. Took me 3 days to solve it and its an elegant solution. One guy I saw was close.

here's some hints, how do you turn a 10 sided die to a 7 sided die?
And then how do you turn a 2 sided die (a coin) into a 4 sided die?

rand5()+randr()+.....12times..
This gives numbers between 12 to 60 uniformly....
so there are 60-12+1 = 49 numbers in total.....
do mod 7 with result and add 1...
this gives 1-7 with equal prob!
same with dice...can be thrown 12 times..n add the results % 7..

Change each five-sided die into a binary digit (1-2 are zero, 3-4 are 1, five is a re-roll) and then roll three of them. Interpret the number as binary, with zero being a re-roll
PS: Found this on someone s blog about their google interview experience

I think there is no possible solution; as there are no common powers of 5 and 7. (Note: rolling a die of 6 sides twice, gives 6^2 = 36 possibilities such that (6^2)%6=0 and a number occuring has equal probabilities from 1 through 6. Thus for this to work with 5 and 7 we need a number x such that (5^x)%7=0. Such a number does not exist. Refer to post by anonymous on relative prime.

Can't we simply do it like this:

floor(rand5() * 7 / 5)?

If you think a little how rand() works, it just gives you a float between 0 and 1, and we just multiply it to get a number within our range.

int dice7() {
while (true) {
int num = 5 * (dice5() - 1) + (dice5() - 1);
if (num < 21) return (num % 7 + 1);
}
}

The idea behind this solution is to use the previously generated random as seed to generate the next random number.

int Random7()
{
static int random7 = 0;
random7 = (Random5() + random7)%7;
return (random7+1);
}

my thought is:
Nos from 1 to 7 can be written in binary form as 000 to 111
Now, throw dice for getting all the binary digits.
if Dice Number != 5, digit = (Dice number) % 2
else throw again.
this way we can find all 3 digits with equal probability and hence the number.

Thoughts invited.

//assuming rand5() returns a number in range 0 to 4
int rand7(){//returns a number in range 0 to 6
    sum = (rand5()+rand5()+rand5()+rand5()+rand5());//0 to 20
    return sum/3;

There are some other answers here:
rosettacode.org/wiki/Seven-sided_dice_from_five-sided_dice

Sorry I'm a noob here, but why can we simply:

roll the 5-sided dice 7 times, and then divide by 5

I realise we won't get whole numbers. But if we are allowed to get non-whole numbers, then would this solution be OK?


I notice people are saying something about "uniform distribution" - and that this is part of the answer as to why the above solution is wrong. Can someone please explain how this works here ... sorry and thanks

Throw the 5 sided die repeatedly until it shows either a 1 or 2.
If it is 1 write down 0. If it is 2 write down 1.

Repeat the above until you have written down 3 digits.

If you have 3 zeros start again from the beginning.

You end up with a non zero 3 bit binary number. i.e. a number between 1 and 7.

throw 5 times, sum up the value of each time and get the remainder of sum % 7.

I had trouble replying to the actual message, so trying to reply here.

This is the reply to the message by Bk:

===== quote begin =======
It has correct solution..
See my method...

1. substract 1 from Rand(5) So that you can have values from 0 to 4.
2. convert value to base 2 i.e. 0 or 1. While doing this consider only 0,1,2,3 values.
If it is value 4 then do random again (This is for balancing probablity of number of 0 and 1)
3. Do this three times to get 3 different bits.
4. Now you will get binary number from 000 to 111
===== quote end =======

Isn't the uniformity of the distribution broken here :"If it is value 4 then do random again"?

It looks like it is.

int rand7(){
return (rand5()+ rand5()+...7 times) % 7
}