{x}
blog image

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:

This problem asks to find the number of distinct roll sequences of a 6-sided dice satisfying two conditions:

  1. The greatest common divisor (GCD) of adjacent values is 1.
  2. There's a gap of more than 2 rolls between equal values.

The solution uses dynamic programming (DP) to efficiently count these sequences. A 3D DP array dp[k][i][j] stores the number of distinct sequences of length k ending with i and j (where i and j represent dice faces).

Approach:

  1. Base Case: For n = 1, there are 6 possible sequences (1, 2, 3, 4, 5, 6). For n = 2, we iterate through all pairs of dice rolls and check if they satisfy conditions 1 and 2.

  2. Recursive Relation: For n > 2, we build upon the results for n-1. For a sequence of length k, we consider the last three rolls: h, i, j. We need to ensure:

    • gcd(i+1, j+1) == 1 (condition 1)
    • i != j (condition 2, avoiding consecutive equal rolls)
    • h != i and h != j (condition 2, ensuring sufficient gap between equal rolls)
    • gcd(h+1, i+1) == 1 (condition 1)

    The number of sequences ending with i and j is the sum of sequences of length k-1 ending with h and i, where h satisfies the above conditions.

  3. Iteration: We iterate through all possible values of k, i, and j, calculating dp[k][i][j] based on the recursive relation.

  4. Final Result: Finally, we sum up all the values in dp[n] to get the total number of distinct sequences of length n.

Time Complexity: O(n * 63) ≈ O(216n). The dominant factor is the three nested loops iterating through k, i, and j. The GCD calculation is O(log(min(a,b))), which is relatively insignificant compared to the nested loops.

Space Complexity: O(n * 62) ≈ O(36n). This is the space used by the 3D DP array.

Code Explanation (Python):

The Python code implements the described DP approach. The gcd function calculates the greatest common divisor using Euclid's algorithm. The main part iteratively fills the dp array and finally sums up the results.

Code Explanation (Java, C++, Go):

The Java, C++, and Go code implementations follow the same logic as the Python code, adapting the syntax and data structures to each language. The key aspects — the 3D DP array, the nested loops, and the GCD calculation — remain consistent across all implementations. The choice of language mainly affects syntax and minor implementation details.