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 thetotal number of distinct sequences possible. Since the answer may be very large, return it modulo 10^9 + 7.

Two sequences are considered distinct if at least one element is different.

Examples

Example 1

1
2
3
4
5
6
7

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

1
2
3
4
5

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 <= 10^4

Solution

Method 1 – Dynamic Programming with State Compression

Intuition

We need to count sequences of dice rolls of length n, where adjacent rolls are coprime and no value repeats within 2 positions. This is a classic DP with state: last two rolls, current position, and value constraints.

Approach

  1. Use DP: dp[pos][last][second_last] = number of ways to reach position pos with last and second_last values.
  2. For each position, try all possible dice values (1..6), skip if not coprime with last, or if equal to last or second_last.
  3. Use memoization to avoid recomputation. Modulo 1e9+7 for large answers.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <vector>
#include <numeric>
using namespace std;
const int MOD = 1e9+7;
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
class Solution {
public:
    int distinctSequences(int n) {
        vector<vector<vector<int>>> dp(n+1, vector<vector<int>>(7, vector<int>(7, -1)));
        function<int(int,int,int)> dfs = [&](int pos, int last, int second_last) {
            if (pos == n) return 1;
            int &res = dp[pos][last][second_last];
            if (res != -1) return res;
            res = 0;
            for (int d = 1; d <= 6; ++d) {
                if (d == last || d == second_last) continue;
                if (last && gcd(d, last) != 1) continue;
                res = (res + dfs(pos+1, d, last)) % MOD;
            }
            return res;
        };
        return dfs(0, 0, 0);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

func gcd(a, b int) int { for b != 0 { a, b = b, a%b }; return a }
func distinctSequences(n int) int {
    mod := int(1e9+7)
    dp := make([][][]int, n+1)
    for i := range dp {
        dp[i] = make([][]int, 7)
        for j := range dp[i] { dp[i][j] = make([]int, 7) }
    }
    var dfs func(pos, last, second_last int) int
    dfs = func(pos, last, second_last int) int {
        if pos == n { return 1 }
        if dp[pos][last][second_last] != 0 { return dp[pos][last][second_last] }
        res := 0
        for d := 1; d <= 6; d++ {
            if d == last || d == second_last { continue }
            if last != 0 && gcd(d, last) != 1 { continue }
            res = (res + dfs(pos+1, d, last)) % mod
        }
        dp[pos][last][second_last] = res
        return res
    }
    return dfs(0, 0, 0)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

import java.util.*;
class Solution {
    int MOD = (int)1e9+7;
    int[][][] dp;
    int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
    public int distinctSequences(int n) {
        dp = new int[n+1][7][7];
        for (int[][] arr : dp) for (int[] a : arr) Arrays.fill(a, -1);
        return dfs(0, 0, 0, n);
    }
    int dfs(int pos, int last, int second_last, int n) {
        if (pos == n) return 1;
        if (dp[pos][last][second_last] != -1) return dp[pos][last][second_last];
        int res = 0;
        for (int d = 1; d <= 6; ++d) {
            if (d == last || d == second_last) continue;
            if (last != 0 && gcd(d, last) != 1) continue;
            res = (res + dfs(pos+1, d, last, n)) % MOD;
        }
        return dp[pos][last][second_last] = res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    val MOD = 1_000_000_007
    lateinit var dp: Array<Array<IntArray>>
    fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
    fun distinctSequences(n: Int): Int {
        dp = Array(n+1) { Array(7) { IntArray(7) { -1 } } }
        fun dfs(pos: Int, last: Int, secondLast: Int): Int {
            if (pos == n) return 1
            if (dp[pos][last][secondLast] != -1) return dp[pos][last][secondLast]
            var res = 0
            for (d in 1..6) {
                if (d == last || d == secondLast) continue
                if (last != 0 && gcd(d, last) != 1) continue
                res = (res + dfs(pos+1, d, last)) % MOD
            }
            dp[pos][last][secondLast] = res
            return res
        }
        return dfs(0, 0, 0)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

from functools import lru_cache
from math import gcd
MOD = 10**9+7
class Solution:
    def distinctSequences(self, n: int) -> int:
        @lru_cache(None)
        def dfs(pos, last, second_last):
            if pos == n: return 1
            res = 0
            for d in range(1, 7):
                if d == last or d == second_last: continue
                if last and gcd(d, last) != 1: continue
                res = (res + dfs(pos+1, d, last)) % MOD
            return res
        return dfs(0, 0, 0)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

use std::collections::HashMap;
fn gcd(a: i32, b: i32) -> i32 { if b == 0 { a } else { gcd(b, a % b) } }
impl Solution {
    pub fn distinct_sequences(n: i32) -> i32 {
        fn dfs(pos: i32, last: i32, second_last: i32, n: i32, memo: &mut HashMap<(i32,i32,i32),i32>) -> i32 {
            if pos == n { return 1; }
            if let Some(&v) = memo.get(&(pos, last, second_last)) { return v; }
            let mut res = 0;
            for d in 1..=6 {
                if d == last || d == second_last { continue; }
                if last != 0 && gcd(d, last) != 1 { continue; }
                res = (res + dfs(pos+1, d, last, n, memo)) % 1_000_000_007;
            }
            memo.insert((pos, last, second_last), res);
            res
        }
        let mut memo = HashMap::new();
        dfs(0, 0, 0, n, &mut memo)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

function gcd(a: number, b: number): number { return b === 0 ? a : gcd(b, a % b); }
function distinctSequences(n: number): number {
    const MOD = 1e9+7;
    const memo = new Map<string, number>();
    function dfs(pos: number, last: number, secondLast: number): number {
        if (pos === n) return 1;
        const key = `${pos},${last},${secondLast}`;
        if (memo.has(key)) return memo.get(key)!;
        let res = 0;
        for (let d = 1; d <= 6; ++d) {
            if (d === last || d === secondLast) continue;
            if (last !== 0 && gcd(d, last) !== 1) continue;
            res = (res + dfs(pos+1, d, last)) % MOD;
        }
        memo.set(key, res);
        return res;
    }
    return dfs(0, 0, 0);
}

Complexity

  • ⏰ Time complexity: O(n * 6 * 6) (since states are position, last, second_last)
  • 🧺 Space complexity: O(n * 6 * 6)