Scale Engineer

Dice Roll Simulation

Hard
#1142Time: O(n * faces). This is a significant improvement as we removed the dependency on `max_rollMax` from the loops.Space: O(n * faces). We use a 2D DP table of size `(n+1) x 6` and a sum array of size `n+1`.1 company
Patterns
Dynamic Programming
Data structures
Array
Companies
Akuna Capital

Prompt

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

Approaches

4 approaches with complexity analysis and trade-offs.

This is a more efficient approach that redefines the DP state to reduce the dimensions of the table and improve the time complexity. Instead of tracking the consecutive count explicitly in the state, we calculate the number of valid sequences by taking the total possible sequences and subtracting the invalid ones. This 'subtraction' principle leads to a faster solution.

Algorithm

  • Define dp[i][j] as the number of valid sequences of length i ending with face j.
  • Define S[i] as the total number of valid sequences of length i, which is sum(dp[i][p]) over all faces p.
  • Base case: S[0] = 1 (for the empty sequence).
  • Iterate i from 1 to n:
    • For each face j from 0 to 5:
      • Start with dp[i][j] = S[i-1], which is the count if there were no constraints.
      • Let k = rollMax[j]. We must subtract the invalid sequences that end with more than k consecutive j's.
      • If i > k, the number of invalid sequences is the number of valid sequences of length i-k-1 that did not end in j. This is S[i-k-1] - dp[i-k-1][j]. Subtract this from dp[i][j].
      • If i == k, there is exactly one invalid sequence (all j's). Subtract 1.
    • Calculate S[i] by summing dp[i][j] over all j.
  • Return S[n].

Walkthrough

Let dp[i][j] be the number of valid sequences of length i ending with face j. Let S[i] be the total number of valid sequences of length i.

To calculate dp[i][j], we can start with the total number of ways to form a sequence of length i-1 (S[i-1]) and append j. This gives us S[i-1] potential sequences.

However, this includes invalid sequences where j is rolled more than rollMax[j] consecutive times. We must subtract these. An invalid sequence of length i ending with rollMax[j] + 1 consecutive j's must have the form ... p j j ... j, where p != j. The prefix ... p has length i - (rollMax[j] + 1). The number of such prefixes is the number of valid sequences of that length that do not end in j, which is S[i - rollMax[j] - 1] - dp[i - rollMax[j] - 1][j]. This gives us our recurrence.

class Solution {    public int dieSimulator(int n, int[] rollMax) {        long MOD = 1_000_000_007;        long[][] dp = new long[n + 1][6];        long[] sum = new long[n + 1];        sum[0] = 1;         for (int i = 1; i <= n; i++) {            long currentSum = 0;            for (int j = 0; j < 6; j++) {                // Initially, assume we can append j to any valid sequence of length i-1                dp[i][j] = sum[i - 1];                                int k = rollMax[j];                if (i > k) {                    // Subtract sequences of length i-k-1 not ending with j                    long toSubtract = (sum[i - k - 1] - dp[i - k - 1][j] + MOD) % MOD;                    dp[i][j] = (dp[i][j] - toSubtract + MOD) % MOD;                } else if (i == k) {                    // Subtract the sequence of all j's                    dp[i][j] = (dp[i][j] - 1 + MOD) % MOD;                }                currentSum = (currentSum + dp[i][j]) % MOD;            }            sum[i] = currentSum;        }         return (int) sum[n];    }}

Complexity

Time

O(n * faces). This is a significant improvement as we removed the dependency on `max_rollMax` from the loops.

Space

O(n * faces). We use a 2D DP table of size `(n+1) x 6` and a sum array of size `n+1`.

Trade-offs

Pros

  • Much faster time complexity than the 3D DP approaches.

  • The DP state is simpler (2D vs 3D).

Cons

  • Still uses linear space with respect to n.

  • The recurrence relation is slightly more complex to derive.

Solutions

class Solution {private  Integer[][][] f;private  int[] rollMax;public  int dieSimulator(int n, int[] rollMax) {    f = new Integer[n][7][16];    this.rollMax = rollMax;    return dfs(0, 0, 0);  }private  int dfs(int i, int j, int x) {    if (i >= f.length) {      return 1;    }    if (f[i][j][x] != null) {      return f[i][j][x];    }    long ans = 0;    for (int k = 1; k <= 6; ++k) {      if (k != j) {        ans += dfs(i + 1, k, 1);      } else if (x < rollMax[j - 1]) {        ans += dfs(i + 1, j, x + 1);      }    }    ans %= 1000000007;    return f[i][j][x] = (int)ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem