Number of Distinct Roll Sequences - Solution & Explanation
Problem Statement
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:
- The greatest common divisor of any adjacent values in the sequence is equal to
1. - There is at least a gap of
2rolls between equal valued rolls. More formally, if the value of theithroll is equal to the value of thejthroll, thenabs(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 <= 104
Approach Overview
Problem 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.
Approach 1: Dynamic Programming with State Transition
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.
Code
Python
JavaScript
Complexity
Time Complexity: O(n*6^2), Space Complexity: O(n*6)
Approach 2: Depth First Search (DFS) with Memoization
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.
Complexity
Time Complexity: O(n*6^3), Space Complexity: O(n*6^2)
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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 |
Video Solution
BiWeekly Contest 81 | 2318. Number of Distinct Roll Sequences • codingMohan • 1,461 views views
Watch 4 more video solutions →Frequently Asked Questions
Is Number of Distinct Roll Sequences easy or hard?
Number of Distinct Roll Sequences Python/Java solution
How to solve Number of Distinct Roll Sequences in O(n)?
What is the best approach for Number of Distinct Roll Sequences?
Is Number of Distinct Roll Sequences asked at Google/Amazon/Meta?
What data structure is used in Number of Distinct Roll Sequences?
What is the time complexity of Number of Distinct Roll Sequences?
Ready to solve this problem?
Practice Number of Distinct Roll Sequences with our built-in code editor and test cases.
Practice on FleetCode