[Solved] Number of Distinct Roll Sequences LeetCode Contest Problem

Number of Distinct Roll Sequences: 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

Solution

Explanation

dp[i][j] means the number of sequence ending with i and j
dp[j][k] = sum(dp[i][j]), where k != i and k != j and gcd(j, k) == 1.

Initialize dp[-1][-1],
since -1 is not on dice and co-prime with any integers.

Complexity

Time O(216n)
Space O(36n)

Python

    def distinctSequences(self, n: int) -> int:
        mod = 10**9 + 7
        dp, dp2 = {(7, 7): 1}, Counter()
        for _ in range(n):
            for i, j in dp:
                for k in range(1, 7):
                    if k != i and k != j and gcd(j, k) == 1:
                        dp2[j, k] = (dp2[j, k] + dp[i, j]) % mod
            dp, dp2 = dp2, Counter()
        return sum(dp.values()) % mod

Explanation:

The previous and current cannot have gcd > 1 hence:
For a previous value of:

1 we can have current value in: [2,3,4,5,6]
2 we can have current value in: [1,3,5]
3 we can have current value in: [1,2,4,5]
4 we can have current value in: [1,3,5]
5 we can have current value in: [1,2,3,4,6]
6 we can have current value in: [1,5]

The first number in the sequence can be any out of [1,2,3,4,5,6], to denote this I have taken m[0] = [1,2,3,4,5,6]
Also previous of previous cannot be equal to the current number. previous of previous is denoted by pprev.

Python3:

def distinctSequences(self, n: int) -> int:
    m = [[1,2,3,4,5,6], 
         [2,3,4,5,6],
         [1,3,5],
         [1,2,4,5],
         [1,3,5],
         [1,2,3,4,6],
         [1,5]]
    mod = (10 ** 9) + 7
    @cache
    def dp(prev, pprev, n):
        if n == 0: return 1
        return sum(dp(x, prev, n - 1) for x in m[prev] if pprev != x) % mod
    return dp(0, 0, n)

C++:

int memo[10001][7][7] = {};
vector<vector<int>> m {{1,2,3,4,5,6},
					   {2,3,4,5,6},
					   {1,3,5},
					   {1,2,4,5},
					   {1,3,5},
					   {1,2,3,4,6},
					   {1,5}};
int mod = 1000000007;
int distinctSequences(int n) {
	return dp(0, 0, n);
}
int dp(int prev, int pprev, int n) {
	if (n == 0) return 1;
	if (memo[n][prev][pprev]) return memo[n][prev][pprev];
	int ans = 0;
	for (int x: m[prev])
		if (x != pprev) ans = (ans + dp(x, prev, n - 1)) % mod;
	return memo[n][prev][pprev] = ans;
}

class Solution {
    private static final int MOD = 1_000_000_007;
    private static final int BASE = 7;
    private Integer[][] MEMO;
    
    public int distinctSequences(int n) {
        MEMO = new Integer[n + 1][BASE * BASE];
        return seq(n, 0);
    }
    
    int seq(int i, int lastTwo) {
        if (i == 0) return 1; // we built one sequence
        
        if (MEMO[i][lastTwo] != null) return MEMO[i][lastTwo];
        
        int res = 0;
        for (int d = 1; d < BASE; d++) {
            int last = lastTwo % BASE;
            int secondLast = lastTwo / BASE;
            
            if (lastTwo != 0 && (gcd(last, d) != 1 || last == d || secondLast == d)) continue;
            
            res += seq(i - 1, last * BASE + d);
            res %= MOD;
        }
        
        return MEMO[i][lastTwo] = res;
    }
    
    private static int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
}

Happy Learning – If you require any further information, feel free to contact me.