2318. Number of Distinct Roll Sequences


Problem Description

In this problem, we're challenged with a dice-rolling scenario. We're given an integer n, which represents the number of times we are to roll a fair six-sided die. Our task is to calculate the number of distinct sequences of these dice rolls with two constraints:

  1. The greatest common divisor (GCD) of any two adjacent rolls must be equal to 1. This means that consecutive numbers in the sequence must be co-prime (i.e., they have no common divisors except for 1).

  2. There must be at least a gap of 2 rolls between equal valued rolls. This means if two rolls have the same value, they cannot be adjacent or have just one roll between them; there must be at least two other rolls separating them.

The goal is to find the total number of such sequences and return this count modulo 10^9 + 7 (a large prime number commonly used to avoid overflow in dynamic programming problems).

Two sequences are considered distinct if they differ in at least one roll. We do not consider the order of the sequences; just the content and arrangement of the numbers in them.

Intuition

To solve this problem, we need to consider the constraints carefully and realise that brute-forcing through all possible sequences is not efficient as the number increases. Instead, we can use dynamic programming to remember certain outcomes and avoid recalculating them.

For the first constraint, we notice that only co-prime numbers can be adjacent. Since we are dealing with a six-sided die, there are not many pairs to consider, and we can quickly determine which pairs are valid.

For the second constraint, we have to remember more than just the last thrown die. We also need to remember the roll before last to ensure that there's a gap of at least two rolls between equal valued rolls.

So, we define a 3D dynamic programming table dp, where dp[i][j][k] represents the count of valid sequences of length i where the last roll is j+1 and the roll before last is k+1.

To build this table, we start with base cases, i.e., sequences of length 2 (since the constraint is only meaningful for sequences longer than 1), and then iteratively calculate the count for longer sequences by adding valid preceding numbers to already built sequences.

To be specific, dp[i][j][k] can be formed by adding a number h+1 before j+1, given that h+1 is co-prime to j+1, h is not equal to j and not equal to k. The iterative process continues until we reach sequences of length n.

At the end, we simply sum up the values in the last layer of our dp table, i.e., all dp[n][i][j] to get the total number of valid sequences, and take the modulo as required by the problem.

The intuition for using modulo operation is to handle the problem of large numbers which can lead to integer overflow issues. Since addition is associative, we can safely apply modulo at each step to keep our intermediate results manageable.

Solution Approach

The provided Python solution is structured around dynamic programming, specifically a three-dimensional array, to keep track of the valid sequences as we build them step by step. Let's break down the implementation details:

  1. Initial Setup

    • A 3-dimensional list dp is initialized of size (n+1) x 6 x 6 filled with zeros. This represents the dynamic programming table where dp[k][i][j] will hold the number of valid sequences of length k where the last roll is i+1 and the roll before the last is j+1.
  2. Base Case

    • Since a single roll can result in any of the 6 faces, the base case for n == 1 immediately returns 6 as the answer.
    • For n == 2, we populate dp[2][i][j] with 1 if i+1 (the first roll) and j+1 (the second roll) are co-prime and not the same number.
  3. Populating the DP Table

    • We iterate for each possible sequence length from 3 up to n. For each length k, we iterate over all pairs of faces (i, j) where i != j and i+1 and j+1 are co-prime. This ensures the first constraint is met.

    • For each such pair (i, j), we look for a valid third number h such that h is different from i and j, and h+1 is co-prime with i+1. This adheres to our second constraint.

    • We update dp[k][i][j] by adding the counts of dp[k-1][h][i] each time we find such a valid h. It means that every valid sequence of length k-1 ending with a sequence h, i can be extended by adding j as the new last number to form a valid sequence of length k.

  4. Handling Modulo

    • To avoid large integer values and potential overflow, we perform modulo 10^9 + 7 operation, which is stored in the variable mod, every time we add to dp[k][i][j].
  5. Computing the Final Answer

    • After populating the dp table for sequences of length n, we iterate through the last layer (dp[-1][i][j]) to sum all valid counts. Here, dp[-1] is equivalent to dp[n].

    • As we collect the sum, we again take the modulo to ensure we have the final result within the required constraints.

In the process, the solution makes use of the gcd function, which calculates the greatest common divisor of two numbers to verify the co-primality condition.

Essentially, we are considering all valid endings of sequences and summing them up. The dynamic programming approach ensures we do not recompute sub-problems and thus efficiently calculates the final result.

Example Walkthrough

Let's illustrate the solution approach with a small example where n = 3. This represents rolling a die three times while adhering to the constraints outlined in the problem description.

Step-by-Step:

  1. Initial Setup: We begin by initializing our 3D list dp of size (n+1) x 6 x 6 with zero values. Since n = 3, our dp list will have dimensions 4 x 6 x 6.

  2. Base Case: For n = 1, the solution is 6 since any face value is possible for a single roll. We don't need to illustrate the base case for n = 1 since our example has n = 3.

    For n = 2, we populate dp[2][i][j] with 1 for co-prime pairs (i, j), considering i != j. Since 1 is co-prime with all numbers, dp[2][0][j] for j=1,2,3,4,5 will get set to 1. Similarly, dp[2][1][0], dp[2][1][2], ..., dp[2][1][5] except when j = 1 because 2 and 2 are not co-prime. We continue this process for all combinations.

  3. Populating the DP Table for n = 3: We want to extend our sequences to length 3.

    • Starting with the sequence ending in 1, 2, for the third roll, i = 1 and j = 2. The valid third number h can be 0, 2, 3, 4, or 5 (corresponding to dice values 1, 3, 4, 5, 6) since they are co-prime with 2 and different from 1.
    • For each valid h, we increment dp[3][2][h] by dp[2][1][h], so dp[3][2][0], dp[3][2][2], ..., dp[3][2][5] all become 1.
  4. Handling Modulo: Since we're dealing with small numbers in this example, the modulo operation doesn't affect the outcome. If we were dealing with larger numbers or longer sequences, we would apply modulo 10^9 + 7 to each update to dp to prevent overflow.

  5. Computing the Final Answer for n = 3: Now, we sum up all the values in dp[3][i][j] (for all i and j) as each represents a valid sequence ending with numbers i+1 and j+1. We then take the final sum modulo 10^9 + 7. In our small example, it's the sum of all the 1 values we've placed in dp[3].

Example Outcome:

By exhaustively iterating through all valid pairings and updating our dp list accordingly for n = 3, we can find that there are 48 distinct sequences meeting the criteria. We determined this by summing all the counts in dp[3] where we populated the dp table for sequences of lengths 2 and 3 as illustrated above.

Python Solution

1class Solution:
2    def distinctSequences(self, length: int) -> int:
3        # If the length is 1, there are six possible distinct dice rolls
4        if length == 1:
5            return 6
6      
7        # Define the modulus for the result to prevent overflow
8        modulus = 10**9 + 7
9      
10        # Initialize a 3D dynamic programming array to store the number of sequences
11        # dp[length][i][j] will represent the number of sequences of length `length`
12        # where `i` is the value of the penultimate roll and `j` is the value of the last roll
13        dp = [[[0] * 6 for _ in range(6)] for _ in range(length + 1)]
14      
15        # Precompute sequences of length 2 considering the GCD and different dice values condition
16        for i in range(6):
17            for j in range(6):
18                if gcd(i + 1, j + 1) == 1 and i != j:
19                    dp[2][i][j] = 1
20      
21        # Use dynamic programming to build up the solution for lengths greater than 2
22        for k in range(3, length + 1):
23            for i in range(6):
24                for j in range(6):
25                    # i and j represent two consecutive rolls, their GCD should be 1
26                    # and their values should be different (dice has 6 faces, numbered 1 to 6)
27                    if gcd(i + 1, j + 1) == 1 and i != j:
28                        # Compute the number of sequences where i and j are the last two rolls
29                        for h in range(6):
30                            # Check the GCD condition and that h is different from i and j
31                            if gcd(h + 1, i + 1) == 1 and h != i and h != j:
32                                # Accumulate the counts from the previous step
33                                dp[k][i][j] += dp[k - 1][h][i]
34      
35        # Initialize the answer to zero
36        ans = 0
37      
38        # Sum up all possible ending sequences to get the total sequences of length `length`
39        for i in range(6):
40            for j in range(6):
41                ans += dp[-1][i][j]
42      
43        # Finally, return the total count modulo the specified modulus
44        return ans % modulus
45
46# Helper function to calculate the Greatest Common Divisor (GCD) of two numbers
47def gcd(a, b):
48    while b:
49        a, b = b, a % b
50    return a
51

Java Solution

1class Solution {
2    // This method calculates the number of distinct sequences that can be formed of length n
3    // with constraints: no two adjacent numbers are the same, no two adjacent numbers have a common
4    // divisor greater than 1, and each number is between 1 and 6 inclusive.
5    public int distinctSequences(int n) {
6        // Base case: if the sequence has only one number, there are 6 possibilities
7        if (n == 1) {
8            return 6;
9        }
10      
11        // Modulo value for the result to prevent overflow
12        final int MOD = (int) 1e9 + 7;
13      
14        // Initialize a 3D dynamic programming array
15        // dp[length][current][previous] will store the number of valid sequences of length 'length',
16        // ending with 'current + 1' and having 'previous + 1' as the second to last number
17        int[][][] dp = new int[n + 1][6][6];
18      
19        // Initialize base cases for sequences of length 2
20        for (int i = 0; i < 6; ++i) {
21            for (int j = 0; j < 6; ++j) {
22                // Two numbers are adjacent in the sequence if they satisfy the constraints
23                if (gcd(i + 1, j + 1) == 1 && i != j) {
24                    dp[2][i][j] = 1;
25                }
26            }
27        }
28      
29        // Build the DP table for lengths greater than 2
30        for (int k = 3; k <= n; ++k) {
31            for (int i = 0; i < 6; ++i) { // 'current' number
32                for (int j = 0; j < 6; ++j) { // 'previous' number
33                    // Check if 'current' and 'previous' satisfy the constraints
34                    if (gcd(i + 1, j + 1) == 1 && i != j) {
35                        // If so, update the dp table for the current sequence state
36                        for (int h = 0; h < 6; ++h) { // the number before 'previous'
37                            // Ensure all three consecutive numbers satisfy the constraints
38                            if (gcd(h + 1, i + 1) == 1 && h != i && h != j) {
39                                dp[k][i][j] = (dp[k][i][j] + dp[k - 1][h][i]) % MOD;
40                            }
41                        }
42                    }
43                }
44            }
45        }
46      
47        // Calculate the final answer by summing up all the valid sequences of length n
48        int ans = 0;
49        for (int i = 0; i < 6; ++i) {
50            for (int j = 0; j < 6; ++j) {
51                ans = (ans + dp[n][i][j]) % MOD;
52            }
53        }
54      
55        // Return the total number of distinct sequences
56        return ans;
57    }
58
59    // Helper method to calculate the Greatest Common Divisor (GCD) of two numbers using the Euclidean algorithm
60    private int gcd(int a, int b) {
61        return b == 0 ? a : gcd(b, a % b);
62    }
63}
64

C++ Solution

1#include <vector>
2
3class Solution {
4public:
5    // Function to find the number of distinct dice throw sequences
6    int distinctSequences(int n) {
7        // Base case: if there's only one dice, there are 6 ways to throw it
8        if (n == 1) return 6;
9
10        // Define the modulo constant for large numbers
11        const int MOD = 1e9 + 7;
12
13        // 3D vector for dynamic programming (dp)
14        // dp[length][previous][second_previous] holds the count of sequences
15        // of length `length` ending with `previous` and `second_previous`
16        std::vector<std::vector<std::vector<int>>> dp(n + 1, std::vector<std::vector<int>>(6, std::vector<int>(6)));
17
18        // Initialize for the case when the dice sequence is of length 2
19        for (int previous = 0; previous < 6; ++previous) {
20            for (int second_previous = 0; second_previous < 6; ++second_previous) {
21                // Ensure the two throw results are co-prime and distinct
22                if (gcd(previous + 1, second_previous + 1) == 1 && previous != second_previous)
23                    dp[2][previous][second_previous] = 1;
24            }
25        }
26
27        // Build the dp table for sequences of length 3 to n
28        for (int length = 3; length <= n; ++length) {
29            for (int previous = 0; previous < 6; ++previous) {
30                for (int second_previous = 0; second_previous < 6; ++second_previous) {
31                    if (gcd(previous + 1, second_previous + 1) == 1 && previous != second_previous) {
32                        for (int third_previous = 0; third_previous < 6; ++third_previous) {
33                            // Ensure no two adjacent dice throws are the same and all are co-prime
34                            if (gcd(third_previous + 1, previous + 1) == 1 && third_previous != previous && third_previous != second_previous)
35                                dp[length][previous][second_previous] = (dp[length][previous][second_previous] + dp[length - 1][third_previous][previous]) % MOD;
36                        }
37                    }
38                }
39            }
40        }
41
42        // Aggregate the counts of all sequences of length `n`
43        int ans = 0;
44        for (int previous = 0; previous < 6; ++previous) {
45            for (int second_previous = 0; second_previous < 6; ++second_previous) {
46                ans = (ans + dp[n][previous][second_previous]) % MOD;
47            }
48        }
49
50        // Return the total count modulus MOD
51        return ans;
52    }
53
54    // Helper function for computing the Greatest Common Divisor (GCD)
55    int gcd(int a, int b) {
56        return b == 0 ? a : gcd(b, a % b);
57    }
58};
59

Typescript Solution

1// Function to find the greatest common divisor (GCD) of two numbers
2function gcd(a: number, b: number): number {
3    return b === 0 ? a : gcd(b, a % b);
4}
5
6// Function to find the number of distinct dice throw sequences
7function distinctSequences(n: number): number {
8    // If there's only one die, there are 6 ways to throw it
9    if (n === 1) return 6;
10
11    // Define the modulo constant for large numbers
12    const MOD: number = 1e9 + 7;
13
14    // 3D array for dynamic programming (dp)
15    // dp[length][previous][secondPrevious] holds the count of sequences
16    // of length `length` ending with `previous` and `secondPrevious`
17    const dp: number[][][] = Array.from({ length: n + 1 }, () =>
18        Array.from({ length: 6 }, () =>
19            Array(6).fill(0)
20        )
21    );
22
23    // Initialize for the case when the dice sequence is of length 2
24    for (let previous = 0; previous < 6; ++previous) {
25        for (let secondPrevious = 0; secondPrevious < 6; ++secondPrevious) {
26            // Ensure the two throw results are co-prime and distinct
27            if (gcd(previous + 1, secondPrevious + 1) === 1 && previous !== secondPrevious) {
28                dp[2][previous][secondPrevious] = 1;
29            }
30        }
31    }
32
33    // Build the dp array for sequences of length 3 to n
34    for (let length = 3; length <= n; ++length) {
35        for (let previous = 0; previous < 6; ++previous) {
36            for (let secondPrevious = 0; secondPrevious < 6; ++secondPrevious) {
37                if (gcd(previous + 1, secondPrevious + 1) === 1 && previous !== secondPrevious) {
38                    for (let thirdPrevious = 0; thirdPrevious < 6; ++thirdPrevious) {
39                        // Ensure no two adjacent dice throws are the same and all are co-prime
40                        if (gcd(thirdPrevious + 1, previous + 1) === 1 && thirdPrevious !== previous && thirdPrevious !== secondPrevious) {
41                            dp[length][previous][secondPrevious] =
42                                (dp[length][previous][secondPrevious] + dp[length - 1][thirdPrevious][previous]) % MOD;
43                        }
44                    }
45                }
46            }
47        }
48    }
49
50    // Aggregate the counts of all sequences of length `n`
51    let totalSequences: number = 0;
52    for (let previous = 0; previous < 6; ++previous) {
53        for (let secondPrevious = 0; secondPrevious < 6; ++secondPrevious) {
54            totalSequences = (totalSequences + dp[n][previous][secondPrevious]) % MOD;
55        }
56    }
57
58    // Return the total count modulus MOD
59    return totalSequences;
60}
61

Time and Space Complexity

The given Python code defines a method distinctSequences which calculates the number of distinct die sequences that can be rolled based on certain constraints. Specifically, it uses dynamic programming with a 3D list to keep track of valid sequences at each step of the process.

Time Complexity:

The time complexity of the provided code is determined by several nested loops:

  1. Initialization of the dp array with zeros has a complexity of O(N * 6 * 6) where N is the number of moves.
  2. The first double loop to initialize the second layer of the dp array runs in O(6 * 6) since it iterates over all pairs of die faces and is done once.
  3. The main triple loop (over k, i, and j) combined with the innermost loop over h has a complexity of O((N - 2) * 6 * 6 * 6). N - 2 comes from the fact that we start from the third layer (k starting at 3) and go up to n layers, each i, j pair is iterated over 6 times for each h.

Combining these factors, we get O(N * 6 * 6 + 6 * 6 + (N - 2) * 6 * 6 * 6) which simplifies to O(N * 6^3) because the cubic term dominates the linear term as N grows.

The final double loop to accumulate the answer runs in O(6 * 6), which is constant and negligible compared to N * 6^3.

Thus, the overall time complexity is O(N * 6^3).

Space Complexity:

The space complexity is determined by the space taken by the dp array, which is a 3D array of size (n + 1) * 6 * 6.

Therefore, the space complexity is O(N * 6^2).

Note: The functions gcd and mod are used but have a constant-time complexity. Adding or modulo operation for ans takes constant space, adding only a trivial amount to the overall space complexity. The space used for iteration variables and the answer variable is also constant.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫