D
DevExCode

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

Master LeetCode problem 470 (Implement Rand10() Using Rand7()), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

470. Implement Rand10() Using Rand7()

Medium
MathRejection SamplingRandomizedProbability and Statistics

Problem Explanation

Explanation

To implement rand10() using rand7(), we need to first understand the concept of rejection sampling. The idea is to generate a number in the desired range by discarding numbers that fall outside that range. In this case, we can call rand7() twice to generate numbers in the range [1, 49]. We then map these numbers to the range [1, 10] by rejecting those greater than 40 and mapping the rest to the range [1, 10].

The expected value for the number of calls to rand7() is around 2.45, as we discard some numbers during the rejection sampling process.

Algorithm:

  1. Generate two random numbers x and y in the range [1, 7].
  2. Calculate num = (x-1) * 7 + y to get a number in the range [1, 49].
  3. If num > 40, reject and repeat the process. Otherwise, return num % 10 + 1.

Time Complexity:

The time complexity of this algorithm is O(1) on average.

Space Complexity:

The space complexity is O(1).

Solution Code

class Solution {
    public int rand10() {
        while (true) {
            int num = (rand7() - 1) * 7 + rand7();
            if (num <= 40) {
                return num % 10 + 1;
            }
        }
    }

    private int rand7() {
        // Assume this is provided
        return 0;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 470 (Implement Rand10() Using Rand7())?

This page provides optimized solutions for LeetCode problem 470 (Implement Rand10() Using Rand7()) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 470 (Implement Rand10() Using Rand7())?

The time complexity for LeetCode 470 (Implement Rand10() Using Rand7()) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 470 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 470 in Java, C++, or Python.

Back to LeetCode Solutions