Problem

You are given a function rand2() that returns 0 or 1 with equal probability. Implement a function rand3() that returns 0, 1, or 2, each with equal probability (i.e., uniformly at random).

You may call rand2() as many times as you like, but you may not use any other randomness source.

Examples

Example 1

1
2
3

Input: (calls to rand3())
Output: 0 (with probability 1/3)
Explanation: Each call to rand3() should return 0, 1, or 2 with equal probability. This is one possible output.

Example 2

1
2
3

Input: (calls to rand3())
Output: 1 (with probability 1/3)
Explanation: Each call to rand3() should return 0, 1, or 2 with equal probability. This is one possible output.

Example 3

1
2
3

Input: (calls to rand3())
Output: 2 (with probability 1/3)
Explanation: Each call to rand3() should return 0, 1, or 2 with equal probability. This is one possible output.
Similar Problems

Solution

Method 1 – Base Conversion and Rejection Sampling

Intuition

The key idea is to use the output of rand2() (which returns 0 or 1 with equal probability) to generate a uniform random number in the range [0, 2]. By combining two calls to rand2(), we can generate numbers in [0, 3]. If the result is 3, we reject and repeat. This ensures each of 0, 1, 2 is equally likely.

For example, if rand2() returns 0 or 1, then two calls can make 00, 01, 10, 11 (i.e., 0, 1, 2, 3). We only want 0, 1, 2, so we reject 3.

Approach

  1. Call rand2() twice to generate a 2-bit number: num = 2 * rand2() + rand2().
  2. If num is 3, reject and repeat step 1.
  3. Otherwise, return num (which is 0, 1, or 2, each with equal probability).
  4. This process ensures uniformity because each valid outcome is equally likely, and the rejection step discards the bias.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
	// Assume rand2() is provided and returns 0 or 1 uniformly at random
	int rand3() {
		int ans;
		while (true) {
			ans = 2 * rand2() + rand2();
			if (ans < 3) return ans;
		}
	}
};
1
2
3
4
5
6
7
8
9

// Assume rand2() is provided and returns 0 or 1 uniformly at random
func rand3() int {
	for {
		ans := 2*rand2() + rand2()
		if ans < 3 {
			return ans
		}
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
	// Assume rand2() is provided and returns 0 or 1 uniformly at random
	public int rand3() {
		int ans;
		while (true) {
			ans = 2 * rand2() + rand2();
			if (ans < 3) return ans;
		}
	}
}
1
2
3
4
5
6
7
8
9

class Solution {
	// Assume rand2() is provided and returns 0 or 1 uniformly at random
	fun rand3(): Int {
		while (true) {
			val ans = 2 * rand2() + rand2()
			if (ans < 3) return ans
		}
	}
}
1
2
3
4
5
6
7

class Solution:
	# Assume rand2() is provided and returns 0 or 1 uniformly at random
	def rand3(self) -> int:
		while True:
			ans = 2 * rand2() + rand2()
			if ans < 3:
				return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

impl Solution {
	// Assume rand2() is provided and returns 0 or 1 uniformly at random
	pub fn rand3() -> i32 {
		loop {
			let ans = 2 * rand2() + rand2();
			if ans < 3 {
				return ans;
			}
		}
	}
}
1
2
3
4
5
6
7
8
9

class Solution {
	// Assume rand2() is provided and returns 0 or 1 uniformly at random
	rand3(): number {
		while (true) {
			const ans = 2 * rand2() + rand2();
			if (ans < 3) return ans;
		}
	}
}

Complexity

  • ⏰ Time complexity: O(1) — Each call to rand3() has a constant expected number of iterations (since 3 out of 4 outcomes are accepted each time).
  • 🧺 Space complexity: O(1) — Only a constant number of variables are used.