# LeetCode 470: Implement Rand10() Using Rand7()

## Problem Restatement

We are given an API:

```python
rand7()
```

It returns a uniformly random integer from `1` to `7`.

We need to implement:

```python
rand10()
```

It must return a uniformly random integer from `1` to `10`.

We may only call `rand7()`. We should not use any other random API. The official problem asks for a uniform random integer in `[1, 10]` using only `rand7()`.

## Input and Output

| Item | Meaning |
|---|---|
| Given API | `rand7()` |
| `rand7()` output | Uniform integer from `1` to `7` |
| Function to implement | `rand10()` |
| `rand10()` output | Uniform integer from `1` to `10` |
| Restriction | Only call `rand7()` |

Function shape:

```python
class Solution:
    def rand10(self) -> int:
        ...
```

## Examples

The test system may call `rand10()` many times.

Example outputs may look like:

```python
[2]
[2, 8]
[3, 8, 10]
```

These are only sample random outputs.

The important requirement is not a fixed output sequence.

The important requirement is that each number from `1` to `10` has equal probability.

## First Thought: Use One `rand7()` Call

A first idea might be:

```python
return rand7()
```

This can only produce numbers from `1` to `7`.

It never produces:

```python
8, 9, 10
```

So it cannot be correct.

Another idea is to scale the result somehow, but scaling `1..7` into `1..10` creates uneven probabilities because `7` outcomes cannot be divided evenly into `10` outcomes.

We need a larger uniform sample space.

## Problem With Direct Mapping

A uniform random generator with `7` outcomes cannot directly produce `10` equally likely outcomes.

To map outcomes evenly, the number of source outcomes must be divisible by the number of target outcomes.

But:

```python
7 % 10 != 0
```

So one call is not enough.

If we call `rand7()` twice, we get:

```python
7 * 7 = 49
```

equally likely outcomes.

Now we can use `40` of them because:

```python
40 % 10 == 0
```

The remaining `9` outcomes are rejected and retried.

## Key Insight

Two calls to `rand7()` can generate a uniform number from `1` to `49`.

Think of the first call as a row and the second call as a column in a `7 x 7` grid.

```python
row = rand7() - 1   # 0 to 6
col = rand7()       # 1 to 7
x = row * 7 + col   # 1 to 49
```

Every value from `1` to `49` is equally likely.

Now accept only values from `1` to `40`.

Since `40` is divisible by `10`, each result from `1` to `10` can receive exactly `4` source values.

Then map:

```python
1..40 -> 1..10
```

using:

```python
(x - 1) % 10 + 1
```

or equivalently for `x <= 40`:

```python
x % 10 + 1
```

Both are uniform, but `(x - 1) % 10 + 1` is easier to reason about.

## Algorithm

Repeat forever:

1. Call `rand7()` twice.
2. Convert the two calls into a number `x` from `1` to `49`.
3. If `x <= 40`, return `(x - 1) % 10 + 1`.
4. Otherwise, reject `x` and try again.

The loop eventually returns with probability `1`.

The chance of accepting on each attempt is:

```python
40 / 49
```

So the expected number of attempts is:

```python
49 / 40
```

That is close to `1`.

## Walkthrough

Suppose:

```python
rand7() -> 3
rand7() -> 5
```

Then:

```python
row = 3 - 1 = 2
col = 5
x = 2 * 7 + 5 = 19
```

Since `19 <= 40`, accept it.

Map it to `1..10`:

```python
(19 - 1) % 10 + 1 = 9
```

So this call returns:

```python
9
```

If instead:

```python
x = 42
```

then `42 > 40`, so we reject it and call `rand7()` twice again.

## Correctness

Each call to `rand7()` is uniform over `1..7`.

Two independent calls create `49` equally likely ordered pairs.

The formula:

```python
x = (rand7() - 1) * 7 + rand7()
```

maps those ordered pairs one-to-one onto the integers from `1` to `49`.

So `x` is uniform over `1..49`.

The algorithm accepts only `1..40`. Since the original distribution is uniform, the accepted value is uniform over `1..40`.

The mapping:

```python
(x - 1) % 10 + 1
```

maps the `40` accepted values onto `1..10`, with exactly `4` accepted values per output.

Therefore, each number from `1` to `10` has the same probability.

So `rand10()` is uniform.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Expected time | `O(1)` | Each attempt succeeds with probability `40 / 49` |
| Worst-case time | Unbounded | Rejection sampling can theoretically reject forever |
| Space | `O(1)` | Only a few variables are used |

The probability of many consecutive rejections decreases exponentially.

## Implementation

```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) -> int:
        while True:
            row = rand7() - 1
            col = rand7()
            x = row * 7 + col

            if x <= 40:
                return (x - 1) % 10 + 1
```

## Code Explanation

The first call gives a zero-based row:

```python
row = rand7() - 1
```

So `row` is from `0` to `6`.

The second call gives a one-based column:

```python
col = rand7()
```

So `col` is from `1` to `7`.

Together:

```python
x = row * 7 + col
```

creates a uniform value from `1` to `49`.

If `x` is at most `40`, we can use it:

```python
if x <= 40:
```

Then:

```python
return (x - 1) % 10 + 1
```

maps it uniformly to `1..10`.

If `x` is `41..49`, the loop repeats.

## Alternative Implementation

Some solutions use a zero-based number from `0` to `48`.

```python
class Solution:
    def rand10(self) -> int:
        while True:
            x = (rand7() - 1) * 7 + (rand7() - 1)

            if x < 40:
                return x % 10 + 1
```

Here, `x` is uniform from `0` to `48`.

We accept `0..39`.

That also gives `40` equally likely values, which map evenly to `1..10`.

## Testing

True randomness cannot be tested with exact equality.

Instead, we test two things:

1. Every output is in the range `1..10`.
2. Over many calls, the counts are roughly balanced.

Example local simulation:

```python
import random
from collections import Counter

def rand7():
    return random.randint(1, 7)

class Solution:
    def rand10(self) -> int:
        while True:
            row = rand7() - 1
            col = rand7()
            x = row * 7 + col

            if x <= 40:
                return (x - 1) % 10 + 1

def run_tests():
    s = Solution()
    counts = Counter()

    trials = 100_000

    for _ in range(trials):
        value = s.rand10()
        assert 1 <= value <= 10
        counts[value] += 1

    print(counts)

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Range check | Confirms `rand10()` only returns `1..10` |
| Large sample count | Helps detect obvious bias |
| Rejection path | Values `41..49` should retry, not map directly |
| Uniformity reasoning | Proven by construction, not by exact sample counts |