Overflow in intermediate arithmetic
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.
Move from brute-force thinking to an efficient approach using math strategy.
Given the API rand7() that generates a uniform random integer in the range [1, 7], write a function rand10() that generates a uniform random integer in the range [1, 10]. You can only call the API rand7(), and you shouldn't call any other API. Please do not use a language's built-in random API.
Each test case will have one internal argument n, the number of times that your implemented function rand10() will be called while testing. Note that this is not an argument passed to rand10().
Example 1:
Input: n = 1 Output: [2]
Example 2:
Input: n = 2 Output: [2,8]
Example 3:
Input: n = 3 Output: [3,8,10]
Constraints:
1 <= n <= 105Follow up:
rand7() function?rand7()?Problem summary: Given the API rand7() that generates a uniform random integer in the range [1, 7], write a function rand10() that generates a uniform random integer in the range [1, 10]. You can only call the API rand7(), and you shouldn't call any other API. Please do not use a language's built-in random API. Each test case will have one internal argument n, the number of times that your implemented function rand10() will be called while testing. Note that this is not an argument passed to rand10().
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Math
1
2
3
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #470: Implement Rand10() Using Rand7()
/**
* The rand7() API is already defined in the parent class SolBase.
* public int rand7();
* @return a random integer in the range 1 to 7
*/
class Solution extends SolBase {
public int rand10() {
while (true) {
int i = rand7() - 1;
int j = rand7();
int x = i * 7 + j;
if (x <= 40) {
return x % 10 + 1;
}
}
}
}
// Accepted solution for LeetCode #470: Implement Rand10() Using Rand7()
func rand10() int {
for {
i := rand7() - 1
j := rand7()
x := i*7 + j
if x <= 40 {
return x%10 + 1
}
}
}
# Accepted solution for LeetCode #470: Implement Rand10() Using Rand7()
# The rand7() API is already defined for you.
# def rand7():
# @return a random integer in the range 1 to 7
class Solution:
def rand10(self):
"""
:rtype: int
"""
while 1:
i = rand7() - 1
j = rand7()
x = i * 7 + j
if x <= 40:
return x % 10 + 1
// Accepted solution for LeetCode #470: Implement Rand10() Using Rand7()
/**
* The rand7() API is already defined for you.
* @return a random integer in the range 1 to 7
* fn rand7() -> i32;
*/
impl Solution {
pub fn rand10() -> i32 {
loop {
let i = rand7() - 1;
let j = rand7();
let x = i * 7 + j;
if x <= 40 {
return (x % 10) + 1;
}
}
}
}
// Accepted solution for LeetCode #470: Implement Rand10() Using Rand7()
/**
* The rand7() API is already defined for you.
* function rand7(): number {}
* @return a random integer in the range 1 to 7
*/
function rand10(): number {
while (true) {
const i = rand7() - 1;
const j = rand7();
const x = i * 7 + j;
if (x <= 40) {
return (x % 10) + 1;
}
}
}
Use this to step through a reusable interview workflow for this problem.
Simulate the process step by step — multiply n times, check each number up to n, or iterate through all possibilities. Each step is O(1), but doing it n times gives O(n). No extra space needed since we just track running state.
Math problems often have a closed-form or O(log n) solution hidden behind an O(n) simulation. Modular arithmetic, fast exponentiation (repeated squaring), GCD (Euclidean algorithm), and number theory properties can dramatically reduce complexity.
Review these before coding to avoid predictable interview regressions.
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.