# Number of Distinct Roll Sequences
**Difficulty:** HARD
[External](https://leetcode.com/problems/number-of-distinct-roll-sequences)
Canonical: https://scaleengineer.com/dsa/problems/number-of-distinct-roll-sequences
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Memoization](https://scaleengineer.com/dsa/patterns/memoization)
**Companies:** [ServiceNow](https://scaleengineer.com/companies/servicenow)
---
## 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:

1. The **greatest common divisor** of any **adjacent** values in the sequence is equal to `1`.
2. There is **at least** a gap of `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 <= 104`

# Approaches
## Top-Down Dynamic Programming (Memoization)
This problem exhibits optimal substructure and overlapping subproblems, making it a good candidate for dynamic programming. A straightforward way to implement a DP solution is using recursion with memoization (a top-down DP approach). We define a recursive function that calculates the number of valid sequences from a given state, and we store the results of subproblems in a memoization table to avoid recomputing them.
**Time:** O(n * 7 * 7 * 6) = O(n). There are O(n) states, and each state's computation involves a loop of size 6. · **Space:** O(n * 7 * 7) = O(n). This is for the memoization table. The recursion stack also contributes O(n) space in the worst case.
**Pros:** Conceptually simpler to derive from the problem's recursive nature.; Correctly solves the problem within the given constraints.
**Cons:** Higher space complexity compared to the optimized iterative approach due to the memoization table.; May lead to a `StackOverflowError` for very large `n` (though `n=10^4` is usually acceptable in modern environments).; Recursive function calls introduce some performance overhead.
### Explanation
The state of our recursive function can be defined by `(index, prev_roll, prev_prev_roll)`, representing the number of ways to complete a valid sequence from the current `index` given the two preceding rolls.

- `index`: The current roll position we are trying to fill (from 0 to n-1).
- `prev_roll`: The value of the roll at `index-1`.
- `prev_prev_roll`: The value of the roll at `index-2`.

We use a 3D array, `memo[n][7][7]`, to store the computed results. The dimension size 7 is used to handle dummy values (like 0) for non-existent previous rolls at the beginning of the sequence.

The function works as follows:

- **Base Case:** When `index == n`, it means we have successfully constructed a valid sequence of length `n`. We return 1.
- **Recursive Step:** For the current `index`, we iterate through all possible die rolls (1 to 6). For each potential roll `curr`, we check if it's valid with respect to `prev_roll` and `prev_prev_roll`. If `curr` is a valid roll, we make a recursive call `solve(index + 1, curr, prev_roll)` and add its result to our total count. The final count for the state `(index, prev_roll, prev_prev_roll)` is stored in the memoization table before being returned.

```java
class Solution {
    int MOD = 1_000_000_007;
    int[][][] memo;
    int[][] gcd_cache;

    private int gcd(int a, int b) {
        if (gcd_cache[a][b] != 0) return gcd_cache[a][b];
        int result = b == 0 ? a : gcd(b, a % b);
        return gcd_cache[a][b] = gcd_cache[b][a] = result;
    }

    public int distinctSequences(int n) {
        memo = new int[n + 1][7][7];
        gcd_cache = new int[7][7];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= 6; j++) {
                Arrays.fill(memo[i][j], -1);
            }
        }
        return solve(0, 0, 0, n);
    }

    private int solve(int index, int prev1, int prev2, int n) {
        if (index == n) {
            return 1;
        }
        if (memo[index][prev1][prev2] != -1) {
            return memo[index][prev1][prev2];
        }

        long count = 0;
        for (int curr = 1; curr <= 6; curr++) {
            if (curr == prev1 || curr == prev2) {
                continue;
            }
            if (prev1 != 0 && gcd(curr, prev1) != 1) {
                continue;
            }
            count = (count + solve(index + 1, curr, prev1, n)) % MOD;
        }

        return memo[index][prev1][prev2] = (int) count;
    }
}
```
### Algorithm
- The state of our recursive function can be defined by `solve(index, prev_roll, prev_prev_roll)`, which calculates the number of ways to complete a valid sequence from the current `index` given the two preceding rolls.
- We use a 3D array, `memo[n][7][7]`, to store the computed results for each state to avoid redundant calculations.
- **Base Case:** When `index == n`, it means we have successfully constructed a valid sequence of length `n`. We return 1.
- **Recursive Step:** For the current `index`, we iterate through all possible die rolls (`curr` from 1 to 6). For each `curr`, we check if it's a valid next roll:
  1. `gcd(curr, prev_roll) == 1` (if `prev_roll` exists).
  2. `curr != prev_roll` and `curr != prev_prev_roll` (to satisfy the gap constraint).
- If `curr` is valid, we make a recursive call `solve(index + 1, curr, prev_roll)` and add its result to our total count (modulo `10^9 + 7`).
- The result for the state `(index, prev_roll, prev_prev_roll)` is stored in the memoization table before being returned.
- The process is initiated by calling `solve(0, 0, 0, n)`, where 0 is a placeholder for non-existent rolls.

## Bottom-Up Dynamic Programming (Space-Optimized)
An alternative to the top-down approach is a bottom-up iterative solution. This approach builds the solution from the smallest subproblem (sequences of length 2) up to the desired length `n`. By carefully analyzing the state transitions, we can observe that computing the results for length `i` only requires the results from length `i-1`. This allows for a significant space optimization, reducing the space complexity from O(n) to O(1).
**Time:** O(n * 6^2) = O(n). The main loop runs `n-2` times. Inside, the operations take O(6*6 + 6*6) which is constant time. Thus, the total time complexity is linear in `n`. · **Space:** O(1). We use a few arrays of constant size (e.g., `7x7`), so the space required does not depend on `n`.
**Pros:** Highly efficient in both time and space.; Constant space complexity makes it suitable for very large `n`.; Avoids recursion overhead and potential stack depth limits.; Iterative solutions can have better performance in practice due to factors like cache locality.
**Cons:** Can be slightly more complex to formulate and implement correctly compared to the recursive solution.
### Explanation
We define a DP state `dp[j][k]` as the number of valid sequences of the current length ending with the roll `k` followed by the roll `j`. The key idea is to build up the solution iteratively.

The state transition to compute the counts for length `i` from `i-1` is as follows: A sequence of length `i-1` ending in `(l, k)` can be extended with a new roll `j` if `j` is valid with respect to `k` and `l`. The conditions are `gcd(j, k) == 1`, `j != k`, and `j != l`. The number of ways to form a sequence ending in `(k, j)` is the sum of ways to form sequences of length `i-1` ending in `(l, k)` for all `l != j`.

This sum can be computed efficiently. Let `S[k]` be the total number of valid sequences of length `i-1` ending with roll `k`. Then the number of sequences of length `i` ending in `(k, j)` is `S[k] - dp[k][j]` (the total minus the cases where the roll before `k` was `j`).

Since the calculation for length `i` only depends on length `i-1`, we only need to store the DP table for the previous length. This reduces space complexity to be constant.

```java
class Solution {
    public int distinctSequences(int n) {
        if (n == 1) {
            return 6;
        }
        int MOD = 1_000_000_007;
        boolean[][] coprime = new boolean[7][7];
        for (int i = 1; i <= 6; i++) {
            for (int j = 1; j <= 6; j++) {
                if (gcd(i, j) == 1) {
                    coprime[i][j] = true;
                }
            }
        }

        long[][] dp = new long[7][7];
        // Base case: sequences of length 2
        for (int j = 1; j <= 6; j++) {
            for (int k = 1; k <= 6; k++) {
                if (j != k && coprime[j][k]) {
                    dp[j][k] = 1;
                }
            }
        }

        // Iterate for lengths 3 to n
        for (int i = 3; i <= n; i++) {
            long[][] next_dp = new long[7][7];
            long[] sums = new long[7];
            // Calculate total sequences of length i-1 ending with k
            for (int k = 1; k <= 6; k++) {
                for (int l = 1; l <= 6; l++) {
                    sums[k] = (sums[k] + dp[k][l]) % MOD;
                }
            }

            // Calculate dp for length i
            for (int j = 1; j <= 6; j++) {
                for (int k = 1; k <= 6; k++) {
                    if (j != k && coprime[j][k]) {
                        // Sum of sequences of length i-1 ending in k, where prev roll was not j
                        long count = (sums[k] - dp[k][j] + MOD) % MOD;
                        next_dp[j][k] = count;
                    }
                }
            }
            dp = next_dp;
        }

        long total = 0;
        for (int j = 1; j <= 6; j++) {
            for (int k = 1; k <= 6; k++) {
                total = (total + dp[j][k]) % MOD;
            }
        }
        return (int) total;
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}
```
### Algorithm
- Define `dp[j][k]` as the number of valid sequences of the current length ending with roll `k` followed by roll `j`.
- Handle the base case `n=1` separately.
- Precompute a `coprime[7][7]` table for O(1) GCD checks.
- Initialize the `dp` table for sequences of length 2. `dp[j][k] = 1` for all valid pairs `(k, j)` where `j != k` and `gcd(j, k) == 1`.
- Iterate for length `i` from 3 to `n`:
  - Create a `next_dp[7][7]` table for length `i`.
  - Calculate `sums[k]`, the total number of valid sequences of length `i-1` ending with roll `k`. This is done by summing `dp[k][l]` over all `l`.
  - For each potential last two rolls `(k, j)` of a length `i` sequence:
    - If `j` and `k` form a valid pair:
      - The number of ways is the count of valid sequences of length `i-1` ending in `k` whose second-to-last roll was not `j`. This is calculated as `(sums[k] - dp[k][j])`.
      - Store this result in `next_dp[j][k]`.
  - After iterating through all `j` and `k`, replace `dp` with `next_dp`.
- After the loop, the total number of sequences of length `n` is the sum of all values in the final `dp` table.

# Solutions
### Java

```java
class Solution {
public
  int distinctSequences(int n) {
    if (n == 1) {
      return 6;
    }
    int mod = (int)1 e9 + 7;
    int[][][] dp = new int[n + 1][6][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;
  }
private
  int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
}

```

### CPP

```cpp
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); }
};

```

### Python

```python
class Solution:
    def distinctSequences(self, n: int) -> int: if n == 1: return 6 mod = 10 ** 9 + 7 dp = [[[0] * 6 for _ in range(6)] for _ in range(n + 1)] for i in range(6): for j in range(6): if gcd(i + 1, j + 1) == 1 and i != j: dp[2][i][j] = 1 for k in range(3, n + 1): for i in range(6): for j in range(6): if gcd(i + 1, j + 1) == 1 and i != j: for h in range(6): if gcd(h + 1, i + 1) == 1 and h != i and h != j: dp[k][i][j] += dp[k - 1][h][i] ans = 0 for i in range(6): for j in range(6): ans += dp[- 1][i][j] return ans % mod

```