470. Implement Rand10() Using Rand7()

470

MediumRandomization, Math and Miscellaneous (FAANG add-on)Uniform range expansion via rejectionRejection sampling

Implement Rand10() Using Rand7()

Given an API rand7() that returns a uniformly random integer in [1,7], implement rand10() that returns a uniformly random integer in [1,10]. You may only call rand7() and must not use any other random source.

Open official problem prompt ↗

In plain English

Turn a fair 7-sided die into a fair 10-sided die using only calls to the 7-sided die, with no bias.

Picture it like this

Rolling two 7-sided dice to fill a 7x7 grid of 49 squares, then keeping only 40 of them (four full sets of ten) and re-rolling whenever you land on one of the 9 leftover squares.

Example

Input: n = 1 (generate one value)
Output: [2]
Why: rand10() returns a single uniformly random integer in [1,10]; 2 is one valid outcome, each value having probability 1/10.

Constraints

1 <= n <= 10^5 (n = number of rand10 calls the judge makes)rand7() is uniform over [1,7]Only rand7() may be used as a randomness source

Pattern lesson

See the pattern, then code

Rejection sampling

↗

Randomization, Math and Miscellaneous (FAANG add-on)

Uniform random selection, sampling streams, number theory, or precision-heavy parsing.. Two independent rand7() calls form a uniform value in [1,49] via (row-1)*7 + col. Take only the first 40 outcomes (a multiple of 10) and map them onto [1,10]; reject 41..49 and retry so no value is favored.

New words, made simpleKnow these before the algorithm

Rejection sampling: Generate from a larger uniform set and discard outcomes outside the desired range, retrying until acceptance.
Uniform composition: (row-1)*7 + col with two independent rand7 draws is uniform over [1,49].
Acceptance region: The 40 kept outcomes, a multiple of 10, so mapping to [1,10] stays even.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Sum/mod of one or two calls

Biased — sums of dice are triangular, not uniform, so values cluster.

Return something like (rand7()+rand7()) % 10 + 1.

Time O(1)Space O(1)

Best choiceReject to [1,40] then mod 10

Unbiased and simple; the standard solution.

Build [1,49], accept the first 40, map to [1,10].

Time O(1) expectedSpace O(1)

Recycle rejected values

Optimizes the follow-up but adds complexity; not needed to pass.

Reuse the leftover 41..49 as a smaller uniform source to cut expected calls.

Time O(1) expected (fewer calls)Space O(1)

The rule we keep true

Invariant

Every accepted idx in [1,40] is equally likely (probability 1/49 each before conditioning), so the 10 residues under (idx-1)%10 each collect exactly four outcomes.

Why this is correct

Reasoning

idx is uniform on [1,49]. Conditioning on idx <= 40 gives a uniform distribution on [1,40]. Since 40 = 4·10, each value 1..10 corresponds to exactly four idx values, so each has conditional probability 4/40 = 1/10.

The algorithm in three movesSay these aloud before coding

1Call rand7() twice to get row and col

row=3, col=5 -> idx=(3-1)*7+5=19

2Compute idx = (row-1)*7 + col, uniform in [1,49]

19 <= 40 -> accept

3If idx <= 40, return (idx-1) % 10 + 1

(19-1)%10+1 = 9

4Otherwise reject and repeat the loop

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1..70

1..72

1..494

1 · Readrow=rand7()=3, col=rand7()=5

2 · AskForm the 49-range value

3 · Update stateidx = 2*7 + 5 = 19

4 · Resultidx=19

Key takeaway

Two rand7 calls index a 7x7 grid of 49 cells; the first 40 map evenly to 1..10, the rest are rejected.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3Retry loop
Keep sampling until an accepted value appears; guarantees termination with probability 1.
2
Lines 4-6Build [1,49]
Two rand7 draws index a 7x7 grid uniformly.
3
Lines 7-8Accept and map
Only the first 40 outcomes are kept, then reduced evenly into [1,10].

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

idx in 41..49 forces a retry — correct, not a failure
row=7,col=7 gives idx=49, always rejected
Very unlucky runs can loop many times but expected calls stay near 2.45

Common beginner mistakes

Accepting all 49 and doing %10 — biases the last 9 values
Using (row-1)*7 + col with col in [0,6] instead of [1,7] — off-by-one breaks uniformity
Returning idx % 10 without the -1/+1 shift, which yields 0 and mis-maps 10

Check your understanding

Why accept only up to 40 rather than all 49 outcomes?

Implement Rand10() Using Rand7()

Implement Rand10() Using Rand7()

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Randomization, Math and Miscellaneous (FAANG add-on)