A die simulator generates a random number from 1 to 6 for each roll. You introduced a constraint to the generator such that it cannot roll the number i more than rollMax[i] (1-indexed) consecutive times.
Given an array of integers rollMax and an integer n, return the number of distinct sequences that can be obtained with exact n rolls. Since the answer may be too large, return it modulo 109 + 7.
Two sequences are considered different if at least one element differs from each other.
Example 1:
Input: n = 2, rollMax = [1,1,2,2,2,3] Output: 34 Explanation: There will be 2 rolls of die, if there are no constraints on the die, there are 6 * 6 = 36 possible combinations. In this case, looking at rollMax array, the numbers 1 and 2 appear at most once consecutively, therefore sequences (1,1) and (2,2) cannot occur, so the final answer is 36-2 = 34.
Example 2:
Input: n = 2, rollMax = [1,1,1,1,1,1] Output: 30
Example 3:
Input: n = 3, rollMax = [1,1,1,2,2,3] Output: 181
Constraints:
1 <= n <= 5000rollMax.length == 61 <= rollMax[i] <= 15When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
This search builds sequences one roll at a time and keeps a face only when it does not extend a run past that face's limit. A sequence is counted only after it reaches exactly the requested length. The final count is the remainder modulo 1,000,000,007.
Here's how the algorithm would work step-by-step:
class Solution:
def dieSimulator(self, number_of_rolls: int, roll_max: list[int]) -> int:
self.valid_sequence_count = 0
def generate_sequences_recursive(current_sequence):
# A complete and valid sequence has been built, so we count it.
if len(current_sequence) == number_of_rolls:
self.valid_sequence_count += 1
return
# Explore adding each possible die face (1-6) as the next roll.
for die_face in range(1, 7):
roll_max_for_face = roll_max[die_face - 1]
# If the sequence is too short to violate the rule, the roll is always valid.
if len(current_sequence) < roll_max_for_face:
generate_sequences_recursive(current_sequence + [die_face])
else:
# Check if adding this roll would violate the consecutive roll constraint.
is_violation = True
for check_index in range(1, roll_max_for_face + 1):
if current_sequence[-check_index] != die_face:
is_violation = False
break
# If the new roll doesn't break the rule, continue exploring this path.
if not is_violation:
generate_sequences_recursive(current_sequence + [die_face])
generate_sequences_recursive([])
return self.valid_sequence_count % (10**9 + 7)This count records how many valid sequences of each length end on each face, together with the total for that length. Extending the length by one face starts from the previous total and then subtracts the extensions whose history would make that face illegal. Every stored count is kept modulo 1,000,000,007.
Here's how the algorithm would work step-by-step:
def dice_roll_simulation(number_of_rolls: int, roll_max: list[int]) -> int:
MOD = 10**9 + 7
number_of_faces = 6
# dp[roll_index][face_value] stores the number of valid sequences of length roll_index ending with face_value.
dp_table = [[0] * (number_of_faces + 1) for _ in range(number_of_rolls + 1)]
# Base case: For one roll, there is exactly one way to get any face.
for face_value in range(1, number_of_faces + 1):
dp_table[1][face_value] = 1
# This array will store the total number of valid sequences for a given length.
total_sequences_at_length = [0] * (number_of_rolls + 1)
total_sequences_at_length[1] = 6
for current_roll_index in range(2, number_of_rolls + 1):
total_sequences_for_previous_length = total_sequences_at_length[current_roll_index - 1]
for current_face_value in range(1, number_of_faces + 1):
# Initially, assume any valid sequence of the previous length can be followed by any face.
dp_table[current_roll_index][current_face_value] = total_sequences_for_previous_length % MOD
max_consecutive = roll_max[current_face_value - 1]
if current_roll_index > max_consecutive:
# We subtract sequences that would be invalidated by adding the current face value.
length_before_bad_sequence = current_roll_index - max_consecutive - 1
total_at_prior_length = total_sequences_at_length[length_before_bad_sequence]
sequences_ending_with_same_face = dp_table[length_before_bad_sequence][current_face_value]
sequences_to_remove = (total_at_prior_length - sequences_ending_with_same_face + MOD) % MOD
dp_table[current_roll_index][current_face_value] = (dp_table[current_roll_index][current_face_value] - sequences_to_remove + MOD) % MOD
# This case handles when the current roll index itself violates the max consecutive rule for a face.
elif current_roll_index == max_consecutive + 1:
dp_table[current_roll_index][current_face_value] = (dp_table[current_roll_index][current_face_value] - 1 + MOD) % MOD
current_total = sum(dp_table[current_roll_index])
total_sequences_at_length[current_roll_index] = current_total % MOD
return total_sequences_at_length[number_of_rolls]| Case | How to Handle |
|---|---|
| Only one roll is requested | Every face is legal on its own, so the count is six when each limit is at least one. |
| Every consecutive limit is one and two rolls are requested | Any immediate repeat is rejected, which removes the six doubles from the thirty-six unrestricted sequences. |
| A face limit is longer than the whole sequence | That face can occupy every roll, because a forbidden run cannot fit inside the sequence. |
| The same face is repeated up to its limit and then interrupted | The run is allowed, and the face may start again after a different face is rolled. |
| The number of rolls is large | The reported count is the remainder modulo 1,000,000,007 so the result stays bounded. |