# 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