You are given an integer n. You roll a fair 6-sided dice n times. Determine the total number of distinct sequences of rolls possible such that the following conditions are satisfied:
1.2 rolls between equal valued rolls. More formally, if the value of the ith roll is equal to the value of the jth roll, then abs(i - j) > 2.Return the total number of distinct sequences possible. Since the answer may be very large, return it modulo 109 + 7.
Two sequences are considered distinct if at least one element is different.
Example 1:
Input: n = 4 Output: 184 Explanation: Some of the possible sequences are (1, 2, 3, 4), (6, 1, 2, 3), (1, 2, 3, 1), etc. Some invalid sequences are (1, 2, 1, 3), (1, 2, 3, 6). (1, 2, 1, 3) is invalid since the first and third roll have an equal value and abs(1 - 3) = 2 (i and j are 1-indexed). (1, 2, 3, 6) is invalid since the greatest common divisor of 3 and 6 = 3. There are a total of 184 distinct sequences possible, so we return 184.
Example 2:
Input: n = 2 Output: 22 Explanation: Some of the possible sequences are (1, 2), (2, 1), (3, 2). Some invalid sequences are (3, 6), (2, 4) since the greatest common divisor is not equal to 1. There are a total of 22 distinct sequences possible, so we return 22.
Constraints:
1 <= n <= 104Problem Overview: You roll a 6-sided die n times. Count how many sequences are valid if two rules hold: adjacent numbers must have gcd(a, b) = 1, and the same value cannot appear with a gap of one position (a[i] != a[i-2]). The task is to compute the total number of distinct sequences modulo 1e9+7.
Approach 1: Depth First Search (DFS) with Memoization (Time: O(n * 6 * 6), Space: O(n * 6 * 6))
This approach models the sequence construction as a recursive search. At each position you try all dice values from 1..6, but only keep values that satisfy the constraints with the previous two rolls. The state is defined by (index, prev, prev2), where prev is the last roll and prev2 is the roll before it. Memoization caches results for each state so the same subproblem is never recomputed. Since there are at most n * 6 * 6 states and each transition checks up to 6 values, the runtime stays linear with respect to n.
Approach 2: Dynamic Programming with State Transition (Time: O(n * 6 * 6), Space: O(6 * 6))
The iterative DP version tracks how many sequences end with a specific pair of values. Define dp[a][b] as the number of sequences where the last two rolls are a then b. For the next roll c, the transition is valid only if gcd(b, c) == 1 and c != a. Iterate over all valid triples (a, b, c) and accumulate counts into the next DP state. Because the die has only 6 faces, the state space is constant (36 pairs), making the algorithm effectively O(n). Space can be reduced to two rolling 6x6 matrices.
Both methods rely on remembering the previous two values because the constraints depend on them. This pattern appears frequently in dynamic programming problems where transitions depend on a fixed history window. The recursive version uses memoization to prune repeated work, while the iterative DP explicitly builds the state transitions.
Recommended for interviews: The Dynamic Programming state transition approach. It demonstrates that you recognized the limited state space and reduced the recursion into a compact iterative DP. Starting with the DFS + memoization formulation is often the easiest way to derive the state definition, but the iterative DP shows stronger control over time and space complexity.
This approach uses dynamic programming to maintain a state for each valid roll configuration. Each state keeps track of possible sequences ending with a particular sequence length, dice face, and ensures no two adjacent faces have a gcd greater than 1. Maintain previous values to ensure same values are not too close.
We use a 2D DP table where dp[i][j] represents the number of ways to roll a sequence of length i ending with the number j. We initialize all sequences of length 1 with 1. For sequences of length > 1, iterate through possible dice values, updating the dp table by considering the constraints. We ensure that rolls have a gcd of 1 and previous values don't repeat nearby by summing valid previous states.
Python
JavaScript
Time Complexity: O(n*6^2), Space Complexity: O(n*6)
The idea behind this approach is to use DFS to explore each possible sequence path that satisfies the conditions and use memoization to store already computed sequence results. This will help us skip redundant calculations and improve efficiency.
We implement DFS with memoization in Java. A map stores results for states defined by the number of remaining rolls and the last two dice values. The DFS function recursively finds valid sequences by checking the gcd and position conditions and memoizes the results to avoid recomputation.
Time Complexity: O(n*6^3), Space Complexity: O(n*6^2)
| Approach | Complexity |
|---|---|
| Dynamic Programming with State Transition | Time Complexity: O(n*6^2), Space Complexity: O(n*6) |
| Depth First Search (DFS) with Memoization | Time Complexity: O(n*6^3), Space Complexity: O(n*6^2) |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS with Memoization | O(n * 6 * 6) | O(n * 6 * 6) | When deriving the recurrence first or explaining the logic recursively |
| Dynamic Programming with State Transition | O(n * 6 * 6) | O(6 * 6) | Best general solution; iterative and memory efficient for large n |
BiWeekly Contest 81 | 2318. Number of Distinct Roll Sequences • codingMohan • 1,412 views views
Watch 4 more video solutions →Practice Number of Distinct Roll Sequences with our built-in code editor and test cases.
Practice on FleetCode