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 <= 104The #2318 Number of Distinct Roll Sequences problem asks you to count valid dice roll sequences of length n while respecting specific constraints such as avoiding consecutive equal values and ensuring certain gcd relationships between neighboring rolls. Because the number of possible sequences grows exponentially, a brute‑force approach quickly becomes infeasible.
A common strategy is to use dynamic programming with memoization. The key idea is to track the last one or two dice values and build sequences incrementally. By defining a state like dp[i][prev][prev2], you can represent the number of valid sequences of length i ending with specific previous rolls. During transitions, enforce constraints such as distinct adjacent values and valid gcd conditions.
Memoization or bottom‑up DP prevents recomputation of overlapping subproblems, making the solution efficient even for larger n. Since the dice faces are limited (1–6), the state space remains manageable.
This optimized approach reduces exponential enumeration to polynomial time while maintaining manageable memory usage.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming with Memoization | O(n * 6 * 6) | O(n * 6 * 6) |
| Optimized State DP | O(n) | O(1) to O(36) |
Greg Hogg
Use these hints if you're stuck. Try solving on your own first.
Can you think of a DP solution?
Consider a state that remembers the last 1 or 2 rolls.
Do you need to consider the last 3 rolls?
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The constraints depend on relationships between consecutive rolls, such as preventing identical neighbors and checking gcd conditions. Tracking previous values ensures each new roll can be validated before extending the sequence.
Problems involving constrained sequence counting and dynamic programming frequently appear in FAANG-style interviews. This question tests state design, DP optimization, and understanding of mathematical constraints like gcd.
A multidimensional DP array or a memoization map works best. These structures store intermediate results for states defined by the current position and previous dice rolls, allowing efficient reuse of computations.
The optimal approach uses dynamic programming with memoization. By tracking the last one or two dice values and enforcing gcd and adjacency constraints, you can build valid sequences incrementally without recomputing overlapping states.