Problem

You are given a function rand01() that returns 0 or 1 with equal probability. Implement a function rand7() (or rand0to6()) that returns an integer from 0 to 6, each with equal probability (i.e., uniformly at random).

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

Examples

Example 1

1
2
3

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

Example 2

1
2
3

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

Solution

Method 1 – Base Conversion and Rejection Sampling

Intuition

The idea is to use multiple calls to rand01() to generate a number in a larger range that covers at least 0 to 6. For example, three calls to rand01() can generate numbers from 0 to 7 (since 2^3 = 8). If the result is 7, we reject and repeat. This ensures each of 0 to 6 is equally likely.

Approach

  1. Call rand01() three times to generate a 3-bit number: num = 4 * rand01() + 2 * rand01() + rand01() (i.e., from 0 to 7).
  2. If num is 7, reject and repeat step 1.
  3. Otherwise, return num (which is 0 to 6, 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 rand01() is provided and returns 0 or 1 uniformly at random
  int rand0to6() {
    int ans;
    while (true) {
      ans = 4 * rand01() + 2 * rand01() + rand01();
      if (ans < 7) return ans;
    }
  }
};
1
2
3
4
5
6
7
8
9

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

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

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

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

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

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

Complexity

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