# Implement Rand10() Using Rand7()
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/implement-rand10-using-rand7)
Canonical: https://scaleengineer.com/dsa/problems/implement-rand10()-using-rand7()
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Randomized](https://scaleengineer.com/dsa/patterns/randomized), [Probability and Statistics](https://scaleengineer.com/dsa/patterns/probability-and-statistics)
**Algorithms:** [Rejection Sampling](https://scaleengineer.com/algorithms/rejection-sampling)
**Companies:** [Tencent](https://scaleengineer.com/companies/tencent)
---
## Problem
Given the **API** `rand7()` that generates a uniform random integer in the range `[1, 7]`, write a function `rand10()` that generates a uniform random integer in the range `[1, 10]`. You can only call the API `rand7()`, and you shouldn't call any other API. Please **do not** use a language's built-in random API.

Each test case will have one **internal** argument `n`, the number of times that your implemented function `rand10()` will be called while testing. Note that this is **not an argument** passed to `rand10()`.

**Example 1:**

**Input:** n = 1
**Output:** [2]

**Example 2:**

**Input:** n = 2
**Output:** [2,8]

**Example 3:**

**Input:** n = 3
**Output:** [3,8,10]

**Constraints:**

* `1 <= n <= 105`

**Follow up:**

* What is the [expected value](https://en.wikipedia.org/wiki/Expected%5Fvalue) for the number of calls to `rand7()` function?
* Could you minimize the number of calls to `rand7()`?

# Approaches
## Rejection Sampling
This approach uses two calls to `rand7()` to generate a number in a larger range, and then rejects values that fall outside a usable sub-range that is a multiple of 10.
**Time:** O(1) on average. The expected number of calls to `rand7()` is constant. The probability of accepting a number in one iteration is `40/49`. The expected number of iterations is `1 / (40/49) = 49/40 = 1.225`. Since each iteration makes 2 calls to `rand7()`, the expected number of `rand7()` calls is `2 * 1.225 = 2.45`. · **Space:** O(1). We only use a few variables to store the intermediate results.
**Pros:** Relatively simple to understand and implement.; Correctly produces a uniform distribution for `rand10()`.
**Cons:** It's not the most efficient in terms of the number of `rand7()` calls. It discards the information from the rejected numbers (41-49), leading to more calls on average.
### Explanation
The core idea is to generate a number in a range larger than 10 and then map it down. A single call to `rand7()` gives 7 outcomes, which is not enough to map to 10 uniform outcomes. Two calls to `rand7()` give `7 * 7 = 49` equally likely outcomes. We can map these 49 outcomes to numbers from 1 to 49. A common way is to use a base-7 mapping: `(rand7() - 1) * 7 + rand7()`. This generates a uniform random integer in the range `[1, 49]`. To get a uniform `rand10()`, we need a range that is a multiple of 10. We can use the numbers from 1 to 40 from our generated range `[1, 49]`. If the generated number is between 1 and 40 (inclusive), we can map it to a number between 1 and 10. The formula `(number - 1) % 10 + 1` achieves this uniformly. If the generated number is greater than 40 (i.e., 41 to 49), we "reject" this result and repeat the entire process by calling `rand7()` twice again. This is necessary to maintain uniformity, as we cannot map the 9 leftover numbers (41-49) to 10 outcomes fairly. This process is repeated until a valid number (1-40) is generated.

```java
/**
 * The rand7() API is already defined in the parent class SolBase.
 * public int rand7();
 * @return a random integer in the range 1 to 7
 */
class Solution extends SolBase {
    public int rand10() {
        while (true) {
            int row = rand7();
            int col = rand7();
            int idx = (row - 1) * 7 + col; // Generates a uniform number in [1, 49]
            if (idx <= 40) {
                return (idx - 1) % 10 + 1;
            }
        }
    }
}
```
### Algorithm
1. Start an infinite loop.
2. Generate a number `idx` from 1 to 49 using the formula: `idx = (rand7() - 1) * 7 + rand7()`. This requires two calls to `rand7()`.
3. Check if `idx` is within the usable range `[1, 40]`.
4. If `idx <= 40`, the number is accepted. Calculate the result as `(idx - 1) % 10 + 1` and return it.
5. If `idx > 40`, the number is rejected. The loop continues, and we try again from step 2.

## Optimized Rejection Sampling by Reusing Rejected Values
This approach improves upon the basic rejection sampling by reusing the information from the rejected numbers to reduce the average number of calls to `rand7()`.
**Time:** O(1) on average. The expected number of calls to `rand7()` is lower than the basic approach. The probability of success with 2 calls is `40/49`. The probability of success with 3 calls is `(9/49) * (60/63)`. The probability of success with 4 calls is `(9/49) * (3/63) * (20/21)`. The expected number of calls is approximately `2.19`, which is a significant improvement over `2.45`. · **Space:** O(1). Only a few variables are needed.
**Pros:** More efficient in terms of the expected number of `rand7()` calls, minimizing waste.; Guarantees a uniform distribution.
**Cons:** The implementation is more complex and less intuitive than the basic rejection sampling method.
### Explanation
This method starts the same way as the basic approach: generate a number `idx` from 1 to 49. If `idx` is in `[1, 40]`, we accept it and return `(idx - 1) % 10 + 1`. The key difference is what happens when `idx > 40`. Instead of discarding the result and starting over, we recognize that we have just generated a uniform random number in the range `[41, 49]`. This is equivalent to generating a uniform random number from 1 to 9 (by subtracting 40). Let's call this `rand9()`. Now, the problem is to generate `rand10()` given a `rand9()` and the `rand7()` function. We can combine our `rand9()` result with a new call to `rand7()` to generate an even larger range. Using the formula `(rand9() - 1) * 7 + rand7()`, we can generate a uniform random number in the range `[1, 63]`. This only required one additional `rand7()` call. From this new range `[1, 63]`, we can use the numbers `[1, 60]`. If our number falls in this range, we return `(number - 1) % 10 + 1`. If the number is in `[61, 63]`, we have generated a `rand3()`. We can repeat the process again: combine this `rand3()` with a new `rand7()` call to get a `rand21()`. From `[1, 21]`, we can use `[1, 20]`. If the number is in this range, we return the result. If the number is 21, we have a `rand1()`, which provides no new randomness. At this point, we have exhausted the utility of the rejected values and must restart the entire process from the beginning. This cascading use of rejected ranges significantly reduces the probability of needing to start over completely, thus lowering the expected number of `rand7()` calls.

```java
/**
 * The rand7() API is already defined in the parent class SolBase.
 * public int rand7();
 * @return a random integer in the range 1 to 7
 */
class Solution extends SolBase {
    public int rand10() {
        while (true) {
            // First attempt: generate rand49, use [1, 40]
            int num49 = (rand7() - 1) * 7 + rand7();
            if (num49 <= 40) {
                return (num49 - 1) % 10 + 1;
            }
            
            // Reuse the rejected range [41, 49] -> [1, 9]
            int num9 = num49 - 40;
            // Second attempt: combine rand9 with rand7 to get rand63, use [1, 60]
            int num63 = (num9 - 1) * 7 + rand7();
            if (num63 <= 60) {
                return (num63 - 1) % 10 + 1;
            }

            // Reuse the rejected range [61, 63] -> [1, 3]
            int num3 = num63 - 60;
            // Third attempt: combine rand3 with rand7 to get rand21, use [1, 20]
            int num21 = (num3 - 1) * 7 + rand7();
            if (num21 <= 20) {
                return (num21 - 1) % 10 + 1;
            }
            
            // Rejected [21], must restart
        }
    }
}
```
### Algorithm
1. Start an infinite loop.
2. **First Level:** Generate `num1 = (rand7() - 1) * 7 + rand7()`. This gives a uniform number in `[1, 49]`.
3. If `num1 <= 40`, return `(num1 - 1) % 10 + 1`.
4. **Second Level:** We have a rejected number from `[41, 49]`. This is a `rand9()`. Let `val9 = num1 - 40`.
5. Generate `num2 = (val9 - 1) * 7 + rand7()`. This gives a uniform number in `[1, 63]`.
6. If `num2 <= 60`, return `(num2 - 1) % 10 + 1`.
7. **Third Level:** We have a rejected number from `[61, 63]`. This is a `rand3()`. Let `val3 = num2 - 60`.
8. Generate `num3 = (val3 - 1) * 7 + rand7()`. This gives a uniform number in `[1, 21]`.
9. If `num3 <= 20`, return `(num3 - 1) % 10 + 1`.
10. **Restart:** The number was 21. This is a `rand1()`. We have no more randomness to extract, so we continue the loop from the beginning.

# Solutions
### Java

```java
/** * The rand7() API is already defined in the parent class SolBase. * public int rand7(); * @return a random integer in the range 1 to 7 */ class Solution extends SolBase { public int rand10 () { while ( true ) { int i = rand7 () - 1 ; int j = rand7 (); int x = i * 7 + j ; if ( x <= 40 ) { return x % 10 + 1 ; } } } }
```

### CPP

```cpp
// The rand7() API is already defined for you. // int rand7(); // @return a random integer in the range 1 to 7 class Solution { public: int rand10 () { while ( 1 ) { int i = rand7 () - 1 ; int j = rand7 (); int x = i * 7 + j ; if ( x <= 40 ) { return x % 10 + 1 ; } } } };
```

### Python

```python
# The rand7() API is already defined for you. # def rand7(): # @return a random integer in the range 1 to 7 class Solution : def rand10 ( self ): """ :rtype: int """ while 1 : i = rand7 () - 1 j = rand7 () x = i * 7 + j if x <= 40 : return x % 10 + 1
```