Number of distinct roll sequences

Dynamic Programming Memoization

58.2% acceptance

Feb 25, 2026

456

You are given an integer n. You roll a fair 6-sided dice n times. Determine the total number of distinct sequences of rolls such that: The greatest common divisor of any adjacent values in the sequence is equal to 1. There is at least a gap of 2 rolls between equal valued rolls (abs(i-j) > 2). Return the total number of distinct sequences possible modulo 10^9 + 7.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn distinct_sequences(n: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let n = n as usize;

    let gcd = |mut a: usize, mut b: usize| -> usize {
      while b != 0 {
        let t = b;
        b = a % b;
        a = t;
      }
      a
    };

    if n == 1 {
      return 6;
    }

    // dp[last][prev] = number of valid sequences ending with (..., prev, last)
    // prev=0 means no previous (length 1 sequence)
    let mut dp = vec![vec![0i64; 7]; 7];
    for v in 1..=6usize {
      dp[v][0] = 1;
    }

    for _ in 1..n {
      let mut ndp = vec![vec![0i64; 7]; 7];
      for last in 1..=6usize {
        for prev in 0..=6usize {
          if dp[last][prev] == 0 {
            continue;
          }
          for cur in 1..=6usize {
            if gcd(cur, last) == 1 && cur != last && cur != prev {
              ndp[cur][last] = (ndp[cur][last] + dp[last][prev]) % MOD;
            }
          }
        }
      }
      dp = ndp;
    }

    let mut ans: i64 = 0;
    for last in 1..=6usize {
      for prev in 0..=6usize {
        ans = (ans + dp[last][prev]) % MOD;
      }
    }
    ans as i32
  }
}