Number of Distinct Roll Sequences solution and explanation
4 more videos on this problem
BiWeekly Contest 81 | 2318. Number of Distinct Roll SequencescodingMohan · 19:29 · 1K views
Leetcode BiWeekly contest 81 - Hard - Number of Distinct Roll SequencesPrakhar Agrawal · 8:31 · 660 views
【每日一题】LeetCode 2318. Number of Distinct Roll SequencesHuifeng Guan · 28:31 · 407 views
2318. Number of Distinct Roll Sequences (Leetcode Hard)Programming Live with Larry · 26:33 · 399 views
2318 Number of Distinct Roll SequencesAnkish Nayak · 9:49 · 107 views
The problem
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.
import math
MOD = 10**9 + 7
def gcd(x, y):
return math.gcd(x, y)
def distinctSequences(n):
dp = [[0]*7 for _ in range(n+1)]
for i in range(1, 7):
dp[1][i] = 1
for i in range(2, n+1):
for j in range(1, 7):
for k in range(1, 7):
if j != k and gcd(j, k) == 1:
dp[i][j] = (dp[i][j] + sum(dp[i-1][x] for x in range(1, 7) if x != j)) % MOD
return sum(dp[n]) % MOD
print(distinctSequences(4)) # Output: 184const MOD = 10**9 + 7;
function gcd(x, y) {
return y === 0 ? x : gcd(y, x % y);
}
function distinctSequences(n) {
const dp = Array.from({length: n+1}, () => Array(7).fill(0));
for (let i = 1; i <= 6; i++) {
dp[1][i] = 1;
}
for (let i = 2; i <= n; i++) {
for (let j = 1; j <= 6; j++) {
for (let k = 1; k <= 6; k++) {
if (j !== k && gcd(j, k) === 1) {
for (let x = 1; x <= 6; x++) {
if (x !== j) {
dp[i][j] = (dp[i][j] + dp[i-1][x]) % MOD;
}
}
}
}
}
}
return dp[n].reduce((a, b) => (a + b) % MOD, 0);
}
console.log(distinctSequences(4)); // Output: 184;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.
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.
import java.util.HashMap;
import java.util.Map;
class Solution {
private static final int MOD = 1000000007;
private Map<String, Long> memo;
public long distinctSequences(int n) {
memo = new HashMap<>();
return dfs(n, 0, 0);
}
private long dfs(int n, int last1, int last2) {
if (n == 0) return 1;
String key = n + "," + last1 + "," + last2;
if (memo.containsKey(key)) return memo.get(key);
long res = 0;
for (int i = 1; i <= 6; i++) {
if (gcd(i, last1) == 1 && i != last2)
res = (res + dfs(n - 1, i, last1)) % MOD;
}
memo.put(key, res);
return res;
}
private int gcd(int x, int y) {
if (y == 0) return x;
return gcd(y, x % y);
}
}
// Usage
Solution sol = new Solution();
System.out.println(sol.distinctSequences(4)); // Output: 184;using System;
using System.Collections.Generic;
public class Solution {
private const int MOD = 1000000007;
private Dictionary<string, long> memo;
public long DistinctSequences(int n) {
memo = new Dictionary<string, long>();
return DFS(n, 0, 0);
}
private long DFS(int n, int last1, int last2) {
if (n == 0) return 1;
string key = n + "," + last1 + "," + last2;
if (memo.ContainsKey(key)) return memo[key];
long result = 0;
for (int i = 1; i <= 6; i++) {
if (GCD(i, last1) == 1 && i != last2)
result = (result + DFS(n - 1, i, last1)) % MOD;
}
memo[key] = result;
return result;
}
private int GCD(int x, int y) {
return y == 0 ? x : GCD(y, x % y);
}
}
// Usage
Solution sol = new Solution();
Console.WriteLine(sol.DistinctSequences(4)); // Output: 184;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 3: Default Approach
class Solution {
public:
int distinctSequences(int n) {
if (n == 1) return 6;
int mod = 1e9 + 7;
vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(6, vector<int>(6)));
for (int i = 0; i < 6; ++i)
for (int j = 0; j < 6; ++j)
if (gcd(i + 1, j + 1) == 1 && i != j)
dp[2][i][j] = 1;
for (int k = 3; k <= n; ++k)
for (int i = 0; i < 6; ++i)
for (int j = 0; j < 6; ++j)
if (gcd(i + 1, j + 1) == 1 && i != j)
for (int h = 0; h < 6; ++h)
if (gcd(h + 1, i + 1) == 1 && h != i && h != j)
dp[k][i][j] = (dp[k][i][j] + dp[k - 1][h][i]) % mod;
int ans = 0;
for (int i = 0; i < 6; ++i)
for (int j = 0; j < 6; ++j)
ans = (ans + dp[n][i][j]) % mod;
return ans;
}
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
};func distinctSequences(n int) int {
if n == 1 {
return 6
}
dp := make([][][]int, n+1)
for k := range dp {
dp[k] = make([][]int, 6)
for i := range dp[k] {
dp[k][i] = make([]int, 6)
}
}
for i := 0; i < 6; i++ {
for j := 0; j < 6; j++ {
if gcd(i+1, j+1) == 1 && i != j {
dp[2][i][j] = 1
}
}
}
mod := int(1e9) + 7
for k := 3; k <= n; k++ {
for i := 0; i < 6; i++ {
for j := 0; j < 6; j++ {
if gcd(i+1, j+1) == 1 && i != j {
for h := 0; h < 6; h++ {
if gcd(h+1, i+1) == 1 && h != i && h != j {
dp[k][i][j] = (dp[k][i][j] + dp[k-1][h][i]) % mod
}
}
}
}
}
}
ans := 0
for i := 0; i < 6; i++ {
for j := 0; j < 6; j++ {
ans = (ans + dp[n][i][j]) % mod
}
}
return ans
}
func gcd(a, b int) int {
if b == 0 {
return a
}
return gcd(b, a%b)
}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 | – |
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 |
Frequently asked questions
Is Number of Distinct Roll Sequences easy or hard?
LeetCode classifies this problem as Hard because it requires modeling multiple constraints in the DP state. The key difficulty is realizing that the last two rolls fully determine whether the next roll is valid.
Number of Distinct Roll Sequences Python/Java solution
Python and Java implementations typically use either a memoized DFS or an iterative DP with a 6x6 matrix. Both enforce the gcd constraint between adjacent rolls and ensure the current value differs from the value two steps earlier.
How to solve Number of Distinct Roll Sequences in O(n)?
Track sequences by the last two dice results. For each pair (a, b), try a new value c such that gcd(b, c) = 1 and c != a. Update counts iteratively for n steps using a 6x6 DP table. Since the state space is fixed, the algorithm scales linearly with n.
What is the best approach for Number of Distinct Roll Sequences?
Dynamic Programming with state transition is the most practical approach. Track the last two dice values and transition only to values that satisfy gcd adjacency and the a[i] != a[i-2] rule. The DP state size is only 36 combinations (6x6), giving an overall time complexity of O(n) and constant space.
Is Number of Distinct Roll Sequences asked at Google/Amazon/Meta?
Problems combining constrained sequence counting and dynamic programming frequently appear in interviews at companies like Google, Amazon, and Meta. Variants often involve dice, gcd constraints, or restricted adjacency rules to test DP state design.
What data structure is used in Number of Distinct Roll Sequences?
A dynamic programming table or memoization cache keyed by the last two dice values. The state typically looks like dp[last][secondLast] or a memo key (index, prev, prev2) in recursive solutions.
What is the time complexity of Number of Distinct Roll Sequences?
The optimal dynamic programming solution runs in O(n * 6 * 6) time, which simplifies to O(n) because the number of dice faces is constant. Each step checks valid transitions between pairs of previous values and the next roll.