Number of Distinct Roll Sequences — Hard Problem & Solution

Roll a standard six-sided die n times. A sequence of rolls is valid when: the greatest common divisor of any two adjacent rolls is 1, and if a value appears…

Difficulty: Hard
Topics: Dynamic Programming, Memoization
Asked at: Amazon, Google, Microsoft
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Roll a standard six-sided die n times. A sequence of rolls is valid when:

the greatest common divisor of any two adjacent rolls is 1, and
if a value appears more than once, the equal rolls are at least 3 apart in the sequence.

Return the number of distinct valid sequences, modulo 10⁹ + 7.

Example 1

Input: n = 1
Output: 6
Explanation: Every single roll is valid.

Example 2

Input: n = 2
Output: 22
Explanation: Of the 36 ordered pairs, 22 are coprime and unequal.

Example 3

Input: n = 4
Output: 184

Constraints

1 <= n <= 10^4

How to solve Number of Distinct Roll Sequences

The constraints reach back exactly two positions, so dp[last][second] — the number of valid sequences ending with second then last — is a complete state. Each step picks a new roll that is coprime with last and differs from both last and second.

Approach

Answer 6 for n = 1.
Seed dp[second][first] = 1 for every ordered pair with first != second and gcd == 1.
Repeat n - 2 times: for each state and each candidate cur, require cur != last, cur != second and gcd(cur, last) == 1, then add into next[cur][last].
Sum the table.

Why it works

The distance rule translates to "differs from the previous two" — a value three apart is allowed, so only the last two matter. That bounds the state at 36 and makes each step constant work, which is what lets n reach 10⁴ without difficulty. A memoised recursion on (index, last, second) is the same DP and is how most solutions are written.

Complexity

Time — O(n · 6³)
Space — O(1) — a 6 × 6 table

Pitfalls

Adjacent equal rolls are already excluded by the gcd rule only for values above 1 — 1, 1 is coprime but still invalid by the distance rule.
The distance is over positions, so a value may reappear exactly three rolls later.
n = 1 and n = 2 need their own handling before the loop begins.

Reference solution

Python

from math import gcd

def distinctSequences(n: int) -> int:
    MOD = 10**9 + 7
    if n == 1:
        return 6
    dp = [[0] * 7 for _ in range(7)]
    for first in range(1, 7):
        for second in range(1, 7):
            if first != second and gcd(first, second) == 1:
                dp[second][first] = 1
    for _ in range(3, n + 1):
        nxt = [[0] * 7 for _ in range(7)]
        for last in range(1, 7):
            for second in range(1, 7):
                ways = dp[last][second]
                if ways == 0:
                    continue
                for cur in range(1, 7):
                    if cur == last or cur == second:
                        continue
                    if gcd(cur, last) != 1:
                        continue
                    nxt[cur][last] = (nxt[cur][last] + ways) % MOD
        dp = nxt
    return sum(sum(row) for row in dp) % MOD

JavaScript

var distinctSequences = function(n) {
    var MOD = 1000000007;
    if (n === 1) return 6;
    var gcd = function(a, b) {
        while (b !== 0) { var t = a % b; a = b; b = t; }
        return a;
    };
    var make = function() {
        var t = [];
        for (var a = 0; a <= 6; a++) {
            var row = [];
            for (var b = 0; b <= 6; b++) row.push(0);
            t.push(row);
        }
        return t;
    };
    var dp = make(), first, second, last, cur;
    for (first = 1; first <= 6; first++) {
        for (second = 1; second <= 6; second++) {
            if (first !== second && gcd(first, second) === 1) dp[second][first] = 1;
        }
    }
    for (var step = 3; step <= n; step++) {
        var next = make();
        for (last = 1; last <= 6; last++) {
            for (second = 1; second <= 6; second++) {
                var ways = dp[last][second];
                if (ways === 0) continue;
                for (cur = 1; cur <= 6; cur++) {
                    if (cur === last || cur === second) continue;
                    if (gcd(cur, last) !== 1) continue;
                    next[cur][last] = (next[cur][last] + ways) % MOD;
                }
            }
        }
        dp = next;
    }
    var total = 0;
    for (var a = 1; a <= 6; a++) {
        for (var b = 1; b <= 6; b++) total = (total + dp[a][b]) % MOD;
    }
    return total;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 195 dynamic programming problems · the whole catalogue