Problem

You are given a function biasedCoin() (or rand2()) that returns 0 or 1 with equal probability (i.e., 50% heads, 50% tails). Write a function that returns 1 with probability 75% and 0 with probability 25%.

Examples

Example 1

1
2

Input: Call the function 10000 times
Output: About 7500 times 1, about 2500 times 0

Example 2

1
2

Input: Call the function once
Output: 1 (with 75% probability), 0 (with 25% probability)
Similar Problems

Solution

Method 1 – Use Two Coin Flips

Intuition

We can use two independent calls to the unbiased coin to generate four equally likely outcomes: (0,0), (0,1), (1,0), (1,1). Assign three of these to 1 and one to 0 to get the desired probabilities.

Approach

  1. Call biasedCoin() twice to get two bits.
  2. If the result is (0,0), return 0 (probability 1/4).
  3. Otherwise, return 1 (probability 3/4).

Code

1
2
3
4
5
6
7

int biasedCoin(); // returns 0 or 1 with 50% probability
int rand75() {
	int a = biasedCoin();
	int b = biasedCoin();
	if (a == 0 && b == 0) return 0;
	return 1;
}
1
2
3
4
5
6
7
8
9

func biasedCoin() int { /* returns 0 or 1 with 50% probability */ }
func rand75() int {
	a := biasedCoin()
	b := biasedCoin()
	if a == 0 && b == 0 {
		return 0
	}
	return 1
}
1
2
3
4
5
6
7

int biasedCoin() { /* returns 0 or 1 with 50% probability */ }
int rand75() {
	int a = biasedCoin();
	int b = biasedCoin();
	if (a == 0 && b == 0) return 0;
	return 1;
}
1
2
3
4
5
6

fun biasedCoin(): Int = /* returns 0 or 1 with 50% probability */
fun rand75(): Int {
	val a = biasedCoin()
	val b = biasedCoin()
	return if (a == 0 && b == 0) 0 else 1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def biasedCoin():
	# returns 0 or 1 with 50% probability
	import random
	return random.randint(0, 1)

def rand75():
	a = biasedCoin()
	b = biasedCoin()
	if a == 0 and b == 0:
		return 0
	return 1
1
2
3
4
5
6

fn biased_coin() -> u8 { /* returns 0 or 1 with 50% probability */ }
fn rand75() -> u8 {
	let a = biased_coin();
	let b = biased_coin();
	if a == 0 && b == 0 { 0 } else { 1 }
}
1
2
3
4
5
6
7
8
9

function biasedCoin(): number {
	// returns 0 or 1 with 50% probability
	return Math.random() < 0.5 ? 0 : 1;
}
function rand75(): number {
	const a = biasedCoin();
	const b = biasedCoin();
	return (a === 0 && b === 0) ? 0 : 1;
}

Complexity

  • ⏰ Time complexity: O(1) — Only two coin flips per call.
  • 🧺 Space complexity: O(1) — No extra space used.