Implement Rand10 Using Rand7

                                            
// The rand7() API is already defined for you.
// int rand7();
// @return a random integer in the range 1 to 7
class Solution {
public:
    int rand10() {
        int rand40 = 40;
        while (rand40 >= 40) {
            rand40 = 7 * (rand7() - 1) + (rand7() - 1);
        }
        return rand40 % 10 + 1;
    }
};

                                            
# The rand7() API is already defined for you.
# def rand7():
# @return a random integer in the range 1 to 7
class Solution(object):
    def rand10(self):
        """
        :rtype: int
        """
        while True:
            num = 7 * (rand7() - 1) + rand7()
            if num <= 40:
                return num % 10 + 1

                                            
// The rand7() API is already defined for you.
// int rand7();
// @return a random integer in the range 1 to 7
int rand10() {
    int val;
    while(true){
        val = (rand7() - 1) * 7 + rand7(); // Generate a number between 1 and 49
        if(val <= 40) return val % 10 + 1; // Return a number between 1 and 10
    }
}

                                            
/**
 * The rand7() API is already defined for you.
 * function rand7(): number {}
 * @return a random integer in the range 1 to 7
 */
function rand10(): number {
    let row = rand7();
    let col = rand7();
    let index = (row - 1) * 7 + col;
    
    while (index > 40) {
        row = rand7();
        col = rand7();
        index = (row - 1) * 7 + col;
    }

    return 1 + (index - 1) % 10;
};

                                            
/*
 * The rand7() API is already defined for you.
 * @return a random integer in the range 1 to 7
 * function rand7();
*/
class Solution {
    /**
     * @param 
     * @return Integer
     */
    function rand10() {
        $result = 7 * (rand7() - 1) + rand7();
        while ($result > 40) {
            $result = 7 * (rand7() - 1) + rand7();
        }
        return 1 + $result % 10;
    }
}

                                            
/**
 * The rand7() API is already defined in the parent class SolBase.
 * func rand7() -> Int = {}
 * @return a random integer in the range 1 to 7
 */
class Solution : SolBase {
    func rand10() -> Int {
        while true {
            let idx = (rand7() - 1) * 7 + rand7()
            if idx <= 40 {
                return 1 + (idx - 1) % 10
            }
        }
    }
}

                                            
/**
 * The rand7() API is already defined in the parent class SolBase.
 * fun rand7(): Int {}
 * @return a random integer in the range 1 to 7
 */
class Solution : SolBase() {
    fun rand10(): Int {
        var row = 0
        var col = 0
        var idx = 0
        do {
            row = rand7()
            col = rand7()
            idx = col + (row - 1) * 7
        } while (idx > 40)
        return 1 + (idx - 1) % 10
    }
}

                                            
func rand10() int {
    for {
        num := (rand7()-1)*7 + rand7() // Generate a random number from 1 to 49
        if num <= 40 {
            return num%10 + 1 // Return number from 1 to 10
        }
    }
}

                                            
# The rand7() API is already defined for you.
# def rand7()
# @return {Integer} a random integer in the range 1 to 7
def rand10()
    while true
        num = (rand7() - 1) * 7 + rand7()
        return num % 10 + 1 if num <= 40
    end
end

                                            
/**
 * The rand7() API is already defined in the parent class SolBase.
 * def rand7(): Int = {}
 * @return a random integer in the range 1 to 7
 */
object Solution extends SolBase {
    def rand10(): Int = {
        var result = 40
        result = rand7() + (rand7() - 1) * 7
        while(result > 40) {
            result = rand7() + (rand7() - 1) * 7
        }
        1 + (result - 1) % 10
    }
}

To solve this coding challenge, we'll leverage the existing

rand7()

API, which provides a uniform random integer from 1 to 7, in order to create a new function

rand10()

that outputs a uniform random integer from 1 to 10. The key challenge here is converting the output range of a uniform random number generator efficiently without introducing significant bias.

Explanation

Here's an in-depth explanation of the methodology we'll employ:

Understanding rand7() Output : The
rand7()

function returns any integer from 1 to 7, each number having an equal probability of 1/7.
Expanding the Range Multiplicatively : By calling
rand7()

twice, we can simulate a larger range of numbers.

The first call to
rand7()

gives us an integer from 1 to 7.
The second call to
rand7()

gives us another integer from 1 to 7.

To fully utilize these results, we think of the first call as choosing a row and the second call as choosing a column in a 7x7 grid, creating a total of 49 possible outcomes (7*7).

Mapping 49 Outcomes to a Useful Range : Since we want a range from 1 to 10:

Generate a number between 1 and 49. Each of these 49 outcomes should have equal probability.
Use only the first 40 outcomes and map them evenly to 1-10. The remaining 9 outcomes (41-49) are discarded, and we repeat the process until we get a valid number within 1-40.

Dividing and Modulo Operation : By leveraging modulo operations, we can map the 40 outcomes to the desired range of 1-10.

Pseudocode with Comments

The pseudocode below describes the detailed steps to solve this problem:

                                            
function rand10():
while True:
# Generate a number in the range [1, 49]
num = (rand7() - 1) * 7 + rand7()

# If the number lies within the first 40 outcomes, map it to [1, 10]
if num <= 40:
return num % 10 + 1
# If the number is outside [1, 40], discard and repeat

The pseudocode efficiently maps the outputs of

rand7()

to an equivalent uniform distribution over the desired range [1, 10]. Here's a breakdown of the inner workings:

Generate Extended Range :

(rand7() - 1) * 7 + rand7()

effectively creates a number in [1, 49].
rand7() - 1

creates a range of [0, 6]. Multiplying by 7 shifts this base by increments of 7.
Adding another
rand7()

call within that extended range gives us all possible combinations in [1, 49].

Discard Unfit Values :

The condition
if num <= 40

ensures only the first 40 numbers are considered, thus maintaining uniform distribution when mapping to [1, 10].
If
num

falls within [41, 49], it is discarded, and the loop continues until a valid number in [1, 40] is produced, ensuring fairness in the final mapping step.

Modulo and Offset :

num % 10

maps values in the set {1-40} directly to sets {0-9}, and adding 1 shifts this to {1-10}.

Detailed Steps in Pseudocode

Initiate Loop :

Continue until a valid number (within 1-40) is found.

First randomized number :

(rand7() - 1) * 7

: Maps rand7() to multiples of 7 (0, 7, 14, ..., 42).

Second randomized number :

Add a second
rand7()

result to span [1, 49].

Check Validity :

Confirm if within 1-40. If not, repeat.

Return Mapped Result :

Use modulo operation and adjust range to return a number between 1 and 10.

By repeatedly generating numbers until a fit within the desired subset is found and using modulo to map these evenly, the approach ensures each possible output from

rand10()

is equally probable.