Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2318.html
2318. Number of Distinct Roll Sequences
- Difficulty: Hard.
- Related Topics: Dynamic Programming, Memoization.
- Similar Questions: Dice Roll Simulation, Paint House III.
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:
-
The greatest common divisor of any adjacent values in the sequence is equal to
1. -
There is at least a gap of
2rolls between equal valued rolls. More formally, if the value of theithroll is equal to the value of thejthroll, thenabs(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
-
class Solution { private int[][][] memo = new int[10001][7][7]; private int mod = 1000000007; private 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} }; public int distinctSequences(int n) { return dp(n, 0, 0); } private int dp(int n, int prev, int pprev) { if (n == 0) { return 1; } if (memo[n][prev][pprev] != 0) { return memo[n][prev][pprev]; } int ans = 0; for (int x : m[prev]) { if (x != pprev) { ans = (ans + dp(n - 1, x, prev)) % mod; } } memo[n][prev][pprev] = ans; return ans; } } ############ class Solution { public int distinctSequences(int n) { if (n == 1) { return 6; } int mod = (int) 1e9 + 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); } } -
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 ############ # 2318. Number of Distinct Roll Sequences # https://leetcode.com/problems/number-of-distinct-roll-sequences/ class Solution: def distinctSequences(self, n: int) -> int: M = 10 ** 9 + 7 res = 0 g = [[False] * 7 for _ in range(7)] for i in range(1, 7): for j in range(1, 7): if gcd(i, j) == 1: g[i][j] = True @cache def go(index, prev1, prev2): if index == n: return 1 res = 0 for dice in range(1, 7): if dice != prev1 and dice != prev2 and (prev1 == 0 or g[dice][prev1]): res += go(index + 1, dice, prev1) res %= M return res % M return go(0, 0, 0) -
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); } }; -
func distinctSequences(n int) int { if n == 1 { return 6 } dp := make([][][]int, n+1) for k := range dp { dp[k] = make([][]int, 6) for i := range dp[k] { dp[k][i] = make([]int, 6) } } for i := 0; i < 6; i++ { for j := 0; j < 6; j++ { if gcd(i+1, j+1) == 1 && i != j { dp[2][i][j] = 1 } } } mod := int(1e9) + 7 for k := 3; k <= n; k++ { for i := 0; i < 6; i++ { for j := 0; j < 6; j++ { if gcd(i+1, j+1) == 1 && i != j { for 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 } } } } } } ans := 0 for i := 0; i < 6; i++ { for j := 0; j < 6; j++ { ans = (ans + dp[n][i][j]) % mod } } return ans } func gcd(a, b int) int { if b == 0 { return a } return gcd(b, a%b) }
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).