# Generate 0 and 1 with 25% and 75% probability

Given a function rand50() that returns 0 or 1 with equal probability, write a function that returns 1 with 75% probability and 0 with 25% probability using rand50() only. Minimize the number of calls to rand50() method. Also, use of any other library function and floating point arithmetic are not allowed.

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

The idea is to use Bitwise OR. A bitwise OR takes two bits and returns 0 if both bits are 0, while otherwise the result is 1. So it has 75% probability that it will return 1.

Below is the implementation of above idea :

## C++

 // Program to print 1 with 75% probability and 0 // with 25% probability #include using namespace std;    // Random Function to that returns 0 or 1 with // equal probability int rand50() {     // rand() function will generate odd or even     // number with equal probability. If rand()     // generates odd number, the function will     // return 1 else it will return 0.     return rand() & 1; }    // Random Function to that returns 1 with 75% // probability and 0 with 25% probability using // Bitwise OR bool rand75() {     return rand50() | rand50(); }    // Driver code to test above functions int main() {     // Intialize random number generator     srand(time(NULL));        for(int i = 0; i < 50; i++)         cout << rand75();        return 0; }

## PHP



/div>

Output:

11101111110010010110011111111101111110111100011000

On similar lines, we can also use Bitwise AND. Since it returns 0 with 75% probability, we have to invert the result.

// Random Function to that returns 1 with 75%
// probability and 0 with 25% probability using
// Bitwise AND
bool rand75()
{
return !(rand50() & rand50());
}

We can replace Bitwise OR and Bitwise AND operator by OR and AND operators as well –

// Random Function to that returns 1 with 75%
// probability and 0 with 25% probability using
// OR or AND operator
int rand75()
{
return !(rand50() && rand50());
// return rand50() || rand50()
}

We can also achieve the result using left shift operator and Bitwise XOR

## C++

 // Program to print 1 with 75% probability and 0 // with 25% probability #include using namespace std;    // Random Function to that returns 0 or 1 with // equal probability int rand50() {     // rand() function will generate odd or even     // number with equal probability. If rand()     // generates odd number, the function will     // return 1 else it will return 0.     return rand() & 1; }    // Random Function to that returns 1 with 75% // probability and 0 with 25% probability using // left shift and Bitwise XOR int rand75() {     // x is one of {0, 1}     int x = rand50();        x = x << 1;        // x is now one of {00, 10}        x = x ^ rand50();        // x is now one of {00, 01, 10, 11}        return (x > 0) ? 1 : 0; }    // Driver code to test above functions int main() {     // Intialize random number generator     srand(time(NULL));        for (int i = 0; i < 50; i++)         cout << rand75();        return 0; }

## PHP

 0) ? 1 : 0; }    // Driver code     // Intialize random // number generator srand(time(NULL));    for (\$i = 0; \$i < 50; \$i++)     echo rand75();        // This code is contributed  // by ajit ?>

Output:

01101110111011000111111111110001111011101110110110

Please note above solutions will produce different results every time we run them.

## tags:

Bit Magic Randomized Bitwise-XOR Bit Magic