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 <= 5000rollMax.length == 61 <= rollMax[i] <= 15
Hints for Dice Roll Simulation
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?
Hint 2
Let
dp[i][j]count legal sequences ofirolls ending in facej, andtotal[i]all legal sequences ofirolls. Appendingjto any legal sequence ofi - 1rolls givestotal[i-1]candidates.Hint 3
The bad candidates are those whose last
rollMax[j]rolls were alreadyjwith a different roll (or nothing) before: there aretotal[i-1-r] - dp[i-1-r][j]of them wheni - 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
total[0] = 1(the empty sequence) anddp[0][j] = 0for every face.- For
ifrom 1 tonand each facejwithr = rollMax[j]:dp[i][j] = total[i-1], minustotal[i-1-r] - dp[i-1-r][j]wheni - 1 - r >= 0. total[i]is the sum ofdp[i][j]over the six faces.- 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 == 0the subtraction istotal[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