Write an algorithm to get 0 and 1 with equal probability using a function which generates random numbers from 1 to 5 with equal probability.

Below is the C implementation (self-explanatory) –

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
#include <stdio.h> #include <stdlib.h> #include <time.h> // Function to generate a random number from 1 to 5 with the // equal probability int random() { return (rand() % 5) + 1; } // Returns 0 or 1 with equal probability using random() function int generate() { int r; do { // r could any one of 1, 2, 3, 4 and 5 r = random(); } while (r == 5); // r could any of 1, 2, 3, 4 now // since there are 2 odd and 2 even numbers, return last bit of r // which could be 0 or 1 with equal probability return r & 1 ; } int main(void) { srand(time(NULL)); int x = 0, y = 0; // make 10000 calls to generate() for (int i = 1; i <= 10000; i++) { generate()? x++: y++; } // print the results printf("0 ~ %0.2f%\n", x/100.0); printf("1 ~ %0.2f%\n", y/100.0); return 0; } |

`Output (will vary): `

0 ~ 50.23%

1 ~ 49.77%

We can also do something like as shown below but this will increase number of calls made to the `random()` function:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
int generate() { int r; do { // r could be { 1, 2, 3, 4, 5} r = random(); } while (r > 2); // r could be 1 or 2 now return r - 1; } |

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply