375. Implement Rand10() Using Rand7()
You have a random generator rand7() that returns a uniform integer in 1…7, and you want to build rand10(), uniform in 1…10. The classic construction is two-roll rejection sampling:
- Take two consecutive
rand7()resultsaandband combine them intov = (a − 1) · 7 + b, which is uniform over1…49. - If
v ≤ 40, accept:rand10()returns((v − 1) mod 10) + 1. - If
v > 40, reject: throw both rolls away and start over with the next pair.
To make this testable, randomness is scripted. Your function receives rolls, the exact sequence of values rand7() will produce, in order. Simulate the construction above, consuming rolls strictly left to right, two at a time; if one roll is left over at the end, ignore it. Return the list of values rand10() produces, in order (possibly empty).
Example 1:
Input: rolls = [1, 3, 6, 6]
Output: [3]
Explanation: Pair (1, 3): v = 0·7 + 3 = 3 ≤ 40, accepted → ((3 − 1) mod 10) + 1 = 3. Pair (6, 6): v = 5·7 + 6 = 41 > 40, rejected.
Example 2:
Input: rolls = [7, 6, 1, 1, 4, 7]
Output: [1, 8]
Explanation: Pair (7, 6): v = 48, rejected. Pair (1, 1): v = 1, accepted → 1. Pair (4, 7): v = 28, accepted → ((28 − 1) mod 10) + 1 = 8.
Example 3:
Input: rolls = [2, 5, 3]
Output: [2]
Explanation: Pair (2, 5): v = 12, accepted → 2. The lone trailing roll 3 has no partner and is ignored.
Constraints:
- 0 ≤ n ≤ 10⁵
- 1 ≤ rolls[i] ≤ 7
- Consume rolls strictly left to right, two at a time; ignore a leftover single roll.
Hints:
Base-7 trick: two rolls a and b give v = (a − 1) · 7 + b, and every value 1…49 corresponds to exactly one (a, b) pair — so v is uniform.
You can't map 49 outcomes onto 10 results evenly (49 isn't a multiple of 10). Keep the first 40 outcomes — each of 1…10 is hit by exactly 4 of them via ((v − 1) mod 10) + 1 — and discard the other 9.
For the simulation, loop an index over the rolls in steps of 2 and stop while at least 2 values remain; emit only accepted pairs.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: rolls = [1, 3, 6, 6]
Expected output: [3]