Dice Roll Simulation - Practice Coding Problems

Dice Roll Simulation - Problem

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 exactly n rolls.

Since the answer may be too large, return it modulo 10⁹ + 7.

Two sequences are considered different if at least one element differs from each other.

Input & Output

Example 1 — Basic Constraint

$ Input: n = 2, rollMax = [1,1,2,2,2,3]

› Output: 34

💡 Note: With 2 rolls and max consecutive limits, we count all valid sequences. For example: [1,2], [1,3], [2,1], [2,3], etc. Invalid: [1,1] (exceeds rollMax[0]=1), [2,2,2] would exceed rollMax[1]=1.

Example 2 — Single Roll

$ Input: n = 1, rollMax = [1,1,1,1,1,1]

› Output: 6

💡 Note: With only 1 roll, all numbers 1-6 are valid since no consecutive constraint is violated. Each number can be rolled once.

Example 3 — High Limits

$ Input: n = 3, rollMax = [1,1,1,1,1,1]

› Output: 181

💡 Note: With 3 rolls and no consecutive repeats allowed, we must alternate numbers. Many valid sequences like [1,2,3], [1,2,4], [2,1,3], etc.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

n=2 rolls, rollMax=[1,1,2,2,2,3] (max consecutive for each die face)

Process

Count all valid sequences respecting consecutive limits

Output

Total number of distinct valid sequences

Key Takeaway

🎯 Key Insight: Track the last rolled number and its consecutive count as state in dynamic programming

Asked in

G Google 15 f Facebook 12 a Amazon 8 M Microsoft 6

The key insight is to use dynamic programming to track the state (position, last number, consecutive count). We can solve this with memoization for O(n × 6 × max(rollMax)) time complexity, or use bottom-up DP for the most efficient solution. Time: O(n × 6 × max(rollMax)), Space: O(n × 6 × max(rollMax))

Common Approaches

Approach	Time	Space	Notes
✓ Recursive Brute Force	O(6^n)	O(n)	Generate all possible sequences recursively and count valid ones
Memoized Dynamic Programming	O(n × 6 × max(rollMax))	O(n × 6 × max(rollMax))	Use memoization to avoid recomputing same states
Bottom-Up Dynamic Programming	O(n × 6 × max(rollMax))	O(n × 6 × max(rollMax))	Build solution iteratively using 3D DP table

Recursive Brute Force — Algorithm Steps

For each position, try rolling numbers 1-6
Track last number and consecutive count
Recursively count valid sequences

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin with empty sequence, try all numbers 1-6

Track State

Keep track of last number and consecutive count

Result

Count all valid complete sequences

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

const int MOD = 1000000007;

int dfs(int pos, int lastNum, int consecutiveCount, int n, int* rollMax) {
    if (pos == n) {
        return 1;
    }
    
    long long total = 0;
    for (int num = 1; num <= 6; num++) {
        if (num == lastNum) {
            if (consecutiveCount < rollMax[num - 1]) {
                total = (total + dfs(pos + 1, num, consecutiveCount + 1, n, rollMax)) % MOD;
            }
        } else {
            total = (total + dfs(pos + 1, num, 1, n, rollMax)) % MOD;
        }
    }
    
    return (int) total;
}

int solution(int n, int* rollMax) {
    return dfs(0, 0, 0, n, rollMax);
}

int main() {
    int n;
    scanf("%d", &n);
    
    int rollMax[6];
    char buffer[100];
    scanf(" %s", buffer);
    
    // Parse [1,1,2,2,2,3] format
    char* ptr = buffer + 1; // skip '['
    for (int i = 0; i < 6; i++) {
        rollMax[i] = strtol(ptr, &ptr, 10);
        if (*ptr == ',') ptr++;
    }
    
    int result = solution(n, rollMax);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(6^n)

Each position has up to 6 choices, leading to exponential possibilities

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth up to n levels

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler