You are given a function:

int rand7()

which returns a uniform random integer from 1 to 7.

Your task:

Implement:

int rand10()

which must return a uniform random integer from 1 to 10, using only rand7().

Example behavior:

rand10() → returns any integer from 1 to 10 with equal probability

---

Problem Understanding

Important constraints:

• You cannot modify rand7()
• You cannot use any other random generator
• Calls to rand7() are allowed multiple times
• Output distribution must be perfectly uniform
• Range size mismatch:
  • rand7 → 7 outcomes
  • rand10 → 10 outcomes

This means:

You cannot simply do:

return rand7() % 10 + 1

because it produces bias.

We need a method that ensures uniform probability across 10 outputs.

---

Logic Explained in Simple English

The key insight:

Use rand7() twice to create a larger random range.

If you call rand7() two times:

(first - 1) * 7 + second

This produces numbers uniformly across:

1 to 49

Now:

• 49 is larger than 10
• The largest multiple of 10 within 49 is 40

So:

1. Generate a value from 1 to 49
2. If the result is within 1–40:
   • Map it to 1–10 uniformly using modulo: return (value - 1) % 10 + 1
3. If value is 41–49:
   • Reject and retry

Why this works:

• 1–40 contains exactly 4 full groups of 10
• Each number 1–10 appears equally
• Rejection ensures no bias

This method is called:

Rejection Sampling

---

Step-by-Step Approach

1. Loop indefinitely
2. Generate: row = rand7() col = rand7() value = (row - 1) * 7 + col // range 1–49
3. If value ≤ 40:
   • return mapped result
4. Else repeat loop

This guarantees uniform probability.

---

Java Implementation

class Solution extends SolBase {
    public int rand10() {
        while (true) {
            int row = rand7();
            int col = rand7();
            int value = (row - 1) * 7 + col;  // 1 to 49

            if (value <= 40) {
                return (value - 1) % 10 + 1;
            }
        }
    }
}

---

Dry Run Example

Suppose rand7() calls return:

row = 5
col = 3

Compute:

value = (5 - 1) * 7 + 3
      = 4 * 7 + 3
      = 31

Since:

31 ≤ 40

Map to 1–10:

(31 - 1) % 10 + 1
= 30 % 10 + 1
= 0 + 1
= 1

So output = 1

Another example:

row = 7
col = 7
value = (7 - 1)*7 + 7 = 49

Since 49 > 40:

Reject and retry

---

Time and Space Complexity

Time Complexity

Expected O(1)

Explanation:

• 40 valid values out of 49 possible
• Acceptance probability = 40/49 ≈ 81.6%
• Expected retries ≈ 1.225

Space Complexity

O(1)

No extra storage.

---

Common Mistakes and How to Avoid Them

Mistake 1: Using modulo directly on rand7()

rand7() % 10 + 1   → biased

Mistake 2: Forgetting uniformity requirement

All 10 values must have exactly equal probability

Mistake 3: Mapping incorrectly

Correct mapping:

(value - 1) % 10 + 1

Mistake 4: Not using rejection sampling

Must discard values above 40

Mistake 5: Thinking rand7()*rand7() works

Multiplication destroys uniformity