Taro Logo

Dice Roll Simulation

#6 Most AskedHard
Topics:
ArraysDynamic Programming

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 <= 5000
  • rollMax.length == 6
  • 1 <= rollMax[i] <= 15

Solution


Clarifying Questions

When 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:

  1. Is the die always six-sided, with one consecutive limit for each face from one through six?
  2. Does a limit restrict only consecutive repeats, so the same face may appear again after a different face?
  3. Must every counted sequence contain exactly the requested number of rolls?
  4. Is the answer the remainder after dividing by 1,000,000,007?
  5. Are two sequences different whenever any one roll differs?

Brute Force Solution

Approach

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:

  1. Start from an empty sequence and a count of zero.
  2. When a sequence already has the requested number of rolls, add one to the count and stop extending it.
  3. Otherwise try each of the six faces as the next roll.
  4. If the sequence is shorter than that face's limit, append the face and keep going, because a forbidden run cannot exist yet.
  5. If the sequence is long enough, inspect the most recent rolls and reject the face when they are already a full run of that face.
  6. When the recent rolls are not such a run, append the face and continue.
  7. After every complete sequence has been considered, return the count modulo 1,000,000,007.

Code Implementation

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)

Big(O) Analysis

Time Complexity
O(n * 6^n) – Let n be the number of rolls. The search forms a tree with one level per roll and up to six choices at each level, which is O(6^n) partial sequences when limits rarely prune a branch. Forming the next sequence copies every roll chosen so far, and those sequences grow to length n, so the copying multiplies the cost by n. The run check inspects only a short fixed suffix, because each limit is a small constant. The modulus is applied once after the search and does not change the bound, so the total time is O(n * 6^n).
Space Complexity
O(n^2) – One path through the search is n calls deep. Each call keeps its own copy of the sequence built so far. Those copies have lengths one through n at the same time, and the sum of those lengths is the triangular number O(n^2). No table of finished answers is stored. When a path returns, its copy can be released, so the extra space is O(n^2).

Optimal Solution

Approach

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:

  1. Record one sequence of length one for each of the six faces, and record six as the total for length one.
  2. Move from length two through the requested number of rolls.
  3. For each face, start from the total number of valid sequences of the previous length.
  4. If the new length is greater than that face's limit, subtract the sequences from the length just before the forbidden run that ended on a different face.
  5. Otherwise, if the new length is exactly one past the limit, subtract one.
  6. Keep each face count as a remainder modulo 1,000,000,007.
  7. Add the six face counts to obtain the total for this length, reduce that total by the same modulus, and return the total for the requested length.

Code Implementation

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]

Big(O) Analysis

Time Complexity
O(n) – Let n be the number of rolls. There is one pass from the second roll through the last. Each length considers six faces, and six does not grow with the input. Updating one face uses a fixed amount of arithmetic and a remainder operation, and adding the six face totals is also constant work. The whole pass is therefore proportional to the number of rolls, which is O(n).
Space Complexity
O(n) – A count is stored for every length and every face, including a starting row before the first roll. The number of faces is the fixed constant six, so the table has one row per roll and a constant number of columns. A second list stores one total per length. Both structures grow in proportion to the number of rolls. The extra space is O(n).

Edge Cases

Only one roll is requested
How to Handle:
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
How to Handle:
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
How to Handle:
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
How to Handle:
The run is allowed, and the face may start again after a different face is rolled.
The number of rolls is large
How to Handle:
The reported count is the remainder modulo 1,000,000,007 so the result stays bounded.
0/19 completed