Dice Roll Simulation

Hard
1505.

Dice Roll Simulation

Dice Roll Simulation is a hard coding problem on arrays and dynamic programming, asked in Amazon and Google interviews.

A die simulator produces a number from 1 to 6 on every roll, but with a restriction: face i may not come up more than rollMax[i - 1] times in a row (the array is 0-indexed, the faces are 1-indexed).

Given n and rollMax, return how many distinct sequences of exactly n rolls the simulator can produce. Two sequences are distinct if they differ in at least one roll. Return the count modulo 10^9 + 7.

Example 1

Input
n = 2, rollMax = [1,2,2,2,2,2]
Output
35
Explanation
Of the 36 two-roll sequences only `(1,1)` is forbidden — face 1 cannot repeat.

Example 2

Input
n = 3, rollMax = [1,1,1,1,1,1]
Output
150
Explanation
No face may repeat: 6 · 5 · 5 sequences.

Example 3

Input
n = 4, rollMax = [3,3,3,3,3,3]
Output
1290
Explanation
Only the six sequences with one face four times running are excluded: 1296 − 6.

Constraints

  • 1 <= n <= 5000
  • rollMax.length == 6
  • 1 <= rollMax[i] <= 15
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[]} rollMax
 * @return {number}
 */
var dieSimulator = function(n, rollMax) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Dice Roll Simulation — Solution in Python, Java & C++

Dice Roll Simulation solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Dice Roll Simulation is a hard coding problem on arrays and dynamic programming, asked in Amazon and Google interviews.

  • Difficulty: Hard
  • Topics: Arrays, Dynamic Programming
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A die simulator produces a number from 1 to 6 on every roll, but with a restriction: face i may not come up more than rollMax[i - 1] times in a row (the array is 0-indexed, the faces are 1-indexed).

Given n and rollMax, return how many distinct sequences of exactly n rolls the simulator can produce. Two sequences are distinct if they differ in at least one roll. Return the count modulo 10^9 + 7.

Example 1

Input: n = 2, rollMax = [1,2,2,2,2,2]
Output: 35
Explanation: Of the 36 two-roll sequences only `(1,1)` is forbidden — face 1 cannot repeat.

Example 2

Input: n = 3, rollMax = [1,1,1,1,1,1]
Output: 150
Explanation: No face may repeat: 6 · 5 · 5 sequences.

Example 3

Input: n = 4, rollMax = [3,3,3,3,3,3]
Output: 1290
Explanation: Only the six sequences with one face four times running are excluded: 1296 − 6.

Constraints

  • 1 <= n <= 5000
  • rollMax.length == 6
  • 1 <= rollMax[i] <= 15

Hints for Dice Roll Simulation

  1. Hint 1

    A sequence stays legal as long as its final run is short enough. What do you need to know about a prefix to extend it?

  2. Hint 2

    Let dp[i][j] count legal sequences of i rolls ending in face j, and total[i] all legal sequences of i rolls. Appending j to any legal sequence of i - 1 rolls gives total[i-1] candidates.

  3. Hint 3

    The bad candidates are those whose last rollMax[j] rolls were already j with a different roll (or nothing) before: there are total[i-1-r] - dp[i-1-r][j] of them when i - 1 - r >= 0. Subtract and reduce modulo 10^9 + 7.

How to solve Dice Roll Simulation

Count sequences by their last face. Appending face j to a legal sequence of i - 1 rolls is illegal only when that sequence already ended in a run of exactly r = rollMax[j] copies of j — and those sequences are in one-to-one correspondence with legal sequences of i - 1 - r rolls that do not end in j.

Approach

  1. total[0] = 1 (the empty sequence) and dp[0][j] = 0 for every face.
  2. For i from 1 to n and each face j with r = rollMax[j]: dp[i][j] = total[i-1], minus total[i-1-r] - dp[i-1-r][j] when i - 1 - r >= 0.
  3. total[i] is the sum of dp[i][j] over the six faces.
  4. Keep everything modulo 10^9 + 7, adding the modulus back after a subtraction. Return total[n].

Why it works

A legal sequence of length i - 1 ending in a run of exactly r copies of j is a legal sequence of length i - 1 - r that does not end in j (possibly the empty one), followed by r copies of j. Appending one more j to it would make a run of r + 1, and it is the only way appending j can break the rule — shorter runs stay legal. So dp[i][j] equals all extensions minus exactly that set, which has total[i-1-r] - dp[i-1-r][j] members.

Complexity

  • Time — O(6 · n)
  • Space — O(6 · n)

Pitfalls

  • The empty prefix counts: when i - 1 - r == 0 the subtraction is total[0] - dp[0][j] = 1.
  • After subtracting, add the modulus before reducing, or languages with truncating % give negative results.
  • total[i] sums six values below 10^9 + 7 — use 64-bit integers.

Reference solution

Python

from typing import List

def dieSimulator(n: int, rollMax: List[int]) -> int:
    MOD = 10 ** 9 + 7
    dp = [[0] * 6 for _ in range(n + 1)]
    total = [0] * (n + 1)
    total[0] = 1
    for i in range(1, n + 1):
        for j in range(6):
            r = rollMax[j]
            v = total[i - 1]
            if i - 1 - r >= 0:
                v -= total[i - 1 - r] - dp[i - 1 - r][j]
            dp[i][j] = v % MOD
        total[i] = sum(dp[i]) % MOD
    return total[n]

Java

public static int dieSimulator(int n, int[] rollMax) {
    final long MOD = 1000000007L;
    long[][] dp = new long[n + 1][6];
    long[] total = new long[n + 1];
    total[0] = 1;
    for (int i = 1; i <= n; i++) {
        long sum = 0;
        for (int j = 0; j < 6; j++) {
            int r = rollMax[j];
            long v = total[i - 1];
            if (i - 1 - r >= 0) v -= total[i - 1 - r] - dp[i - 1 - r][j];
            v = ((v % MOD) + MOD) % MOD;
            dp[i][j] = v;
            sum += v;
        }
        total[i] = sum % MOD;
    }
    return (int) total[n];
}

C++

int dieSimulator(int n, vector<int>& rollMax) {
    const long long MOD = 1000000007LL;
    vector<vector<long long>> dp(n + 1, vector<long long>(6, 0));
    vector<long long> total(n + 1, 0);
    total[0] = 1;
    for (int i = 1; i <= n; i++) {
        long long sum = 0;
        for (int j = 0; j < 6; j++) {
            int r = rollMax[j];
            long long v = total[i - 1];
            if (i - 1 - r >= 0) v -= total[i - 1 - r] - dp[i - 1 - r][j];
            v = ((v % MOD) + MOD) % MOD;
            dp[i][j] = v;
            sum += v;
        }
        total[i] = sum % MOD;
    }
    return (int)total[n];
}

JavaScript

var dieSimulator = function(n, rollMax) {
    var MOD = 1000000007;
    var dp = [], total = new Array(n + 1).fill(0);
    for (var i = 0; i <= n; i++) dp.push([0, 0, 0, 0, 0, 0]);
    total[0] = 1;
    for (var i = 1; i <= n; i++) {
        var sum = 0;
        for (var j = 0; j < 6; j++) {
            var r = rollMax[j], v = total[i - 1];
            if (i - 1 - r >= 0) v -= total[i - 1 - r] - dp[i - 1 - r][j];
            v = ((v % MOD) + MOD) % MOD;
            dp[i][j] = v;
            sum += v;
        }
        total[i] = sum % MOD;
    }
    return total[n];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming