We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Dice Roll Simulation

Difficulty: Hard

Problem Description

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 10^9 + 7. Two sequences are considered different if at least one element differs from each other.

Key Insights

  • We need to generate sequences of rolls while adhering to the constraints given by the rollMax array.
  • Dynamic programming is a suitable approach to keep track of the number of valid sequences as we build them step by step.
  • We can use a 2D DP array where dp[i][j] represents the number of valid sequences of length i that end with the number j.
  • We must consider the maximum consecutive occurrences of each die face as specified in rollMax.

Space and Time Complexity

Time Complexity: O(n * 6 * max(rollMax))
Space Complexity: O(n * 6)

Solution

To solve this problem, we will utilize dynamic programming. We will maintain a 2D list (or array) dp where dp[i][j] will store the number of valid sequences of length i that end with the die face j.

  1. Initialize the dp array for the first roll. Each face can be rolled once.
  2. Iterate through each roll from 1 to n.
  3. For each die face from 1 to 6, calculate the number of valid sequences that can end with this face by considering:
    • The sequences formed by the previous roll with a different face.
    • The sequences formed by the same face but adhering to the rollMax constraint.
  4. Sum the possibilities and store the result in the dp array.
  5. Finally, sum all valid sequences of length n and return the result modulo 10^9 + 7.

Code Solutions

def dieSimulator(n, rollMax):
    MOD = 10**9 + 7
    dp = [[0] * 6 for _ in range(n + 1)]
    for j in range(6):
        dp[1][j] = 1  # One way to have one roll for each face

    for i in range(2, n + 1):
        for j in range(6):
            total = 0
            for k in range(6):
                if k != j:
                    total += sum(dp[i - 1])  # Add all sequences ending with a different face
                else:
                    for m in range(1, rollMax[j] + 1):
                        if m <= i - 1:
                            total += dp[i - m][j]  # Add sequences with the same face up to rollMax
            dp[i][j] = total % MOD

    return sum(dp[n]) % MOD
← Back to All Questions