Get this book -> Problems on Array: For Interviews and Competitive Programming

Given a function that generates 0, 1 50% of the time (like most of the random function in modern programming languages do), how can we design a function that return 0, 1 25%, 75% of the time?

Let's lay out a rule: random functions that return floating points are not allowed to be used. One can only use the said function that returns 0, 1 in equal probability since one can easily set a floating point as a threshold and return 0, 1 according to the exceedance threshold values.

## 📚Content

- Maths and Concept
- Code implementation
- Complexity
- Result
- Challenge

## 📐Maths and Concept

Let's revisit some basic Maths for probability.

We are given a function tha returns a 0, 1 with probability equal to 50%, we name it as *P(0=50% & 1=50%), P(0) = 0.5 and . How can we design an algorithm which uses *P(0=50% & 1=50%)* to achieve the said title?

To design P(0=25% & 1=75%), we propose two different methods.

### OR operator

In short, we can perform one OR operator to achieve our goal:

*P(0=25% & 1=75%) = P(0=50% & 1=50%) || P(0=50% & 1=50%)*

The "||" operator performs OR operation. Here are all the result for such operation:

- 0 || 0 = 0
- 0 || 1 = 1
- 1 || 0 = 1
- 1 || 1 = 1

Since P(0=50% & 1=50%) splits out 0, 1 with equal probability, each row at the above list has 25% of happening (Multiplication of the probability of two independent events). We can thus see that it hs only 1 out of 4 chance of getting a 0, thus 25%. At the same time, it has a 75% obtaining a 1.

### Bitwise exclusive OR operator

There is another way to perform calculation for P(0=25% & 1=75%), by bit shifting and bitwise exclusive OR operation. It has the following pseudocode:

```
function bitwiserand75():
# either {0, 1}
set x to rand50()
# either {00, 10}
x = x << 1
# either {00, 01, 10, 11}
# XOR operator, set each bit to 1 if only
# one of two bits is 1
x = x ^ rand50()
if x > 0:
return 1
return 0
```

The above pseudocode is quite straight foward, but readers may not be very familiar with XOR operation. In short, it sets each bit to 1 if only one of the two bits is 1. Here are some examples:

- 00 ^ 00 = 00
- 00 ^ 01 = 01
- 10 ^ 00 = 10
- 10 ^ 01 = 11

This, we get all the permutation of 0, 1 in a two digit binary setting. Looking at the above list, we know that 0, or 00 happens at 1 out of 4 times, if we set the threshold of returning 1 to be larger than 0, we have a 3 out of 4 chance to obtain a 1, thus 75%.

## 🖥️ Code implementation

Here is the code for implementing the two algorithms described in above section:

```
import random
class baisedGenerator:
# Generator with 50% of 0 and 1
def rand50(self):
return random.randint(0, 1)
# Associated with OR operator
# Generator with 75% of 0 and 1
def rand75(self):
return self.rand50() or self.rand50()
# Associated with bitwise shifting operator
# Generator with 75% of 0 and 1 by bitwise shifting
def bitwiserand75(self):
x = self.rand50()
x = x << 1
x = x ^ self.rand50()
if x > 0:
return 1
return 0
```

## ⏳Complexities

### Time complexity

The above two methods has **constant runtime complexity** since the random module from python gives a random (0, 1) in constant time, and all multiplications, bitshifting and XOR operation takes O(1) to run.

### Space complexity

The above two methods for baised generator do not require additional memory, thus **constant auxiliary space**.

## ✍🏻Result

One can simply aggregate the result by declaring a simple for loop and but printing out the result:

```
g = baisedGenerator()
for i in range(1, 101):
print(g.rand75(), end=" ")
if i%10 == 0:
print()
print()
for i in range(1, 101):
print(g.bitwiserand75(), end=" ")
if i%10 == 0:
print()
```

Here is the result, with around 75% out of 100 that it prints 1 for both methods:

```
1 1 1 1 1 1 1 0 1 0
1 0 1 0 1 1 1 1 1 1
0 1 0 1 1 1 0 1 0 1
1 1 1 1 0 1 1 1 1 0
1 1 1 0 0 0 0 1 1 1
1 1 1 1 1 0 1 0 0 1
1 1 1 1 1 1 0 1 1 1
0 0 1 1 1 1 1 1 1 0
0 1 1 1 1 1 1 1 1 1
0 1 1 1 1 0 1 1 0 1
1 1 0 0 0 0 1 1 1 1
0 1 1 1 0 1 1 1 0 1
1 0 1 1 1 0 1 1 1 1
1 1 1 1 1 1 0 1 1 0
0 0 1 1 0 0 1 1 1 1
1 1 1 1 1 1 1 1 1 0
1 0 1 0 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 0 0 0 1 1 1 1 1
0 1 1 1 1 1 1 0 1 1
```

With this article at OpenGenus, you must have the complete idea of how to generate 0 and 1 with 25% and 75% probability.

## 🧠Challenge

Here you go, an easy non-floating point-based baised generator that gives 0 and 1 in 25% and 75%, but can you use the AND operator instead of OR operator to generate the same distribution of 0 and 1, assuming other rules unchanged?