We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Distinct Roll Sequences

Difficulty: Hard

Problem Description

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.

Return the total number of distinct sequences possible. Since the answer may be very large, return it modulo 10^9 + 7.

Key Insights

  • The maximum possible values for dice rolls are limited to 6.
  • The greatest common divisor condition means that adjacent numbers must be coprime.
  • The gap condition ensures that the same number cannot appear within two rolls of each other.
  • Dynamic programming can be utilized to build solutions iteratively based on previous results.

Space and Time Complexity

Time Complexity: O(n * 6^2)
Space Complexity: O(n * 6)

Solution

To solve this problem, we can use dynamic programming. We maintain a 2D array dp[i][j] where i represents the roll position (from 1 to n) and j represents the dice face (from 1 to 6). The value dp[i][j] will store the number of valid sequences of length i ending with the value j.

The transitions will involve checking the previous two rolls to ensure that they do not contain the same value and that the GCD condition holds. We can sum up the valid sequences from the previous roll based on these conditions.

The result will be the sum of all valid sequences of length n.

Code Solutions

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def distinctRollSequences(n):
    MOD = 10**9 + 7
    dp = [[0] * 7 for _ in range(n + 1)]
    
    for j in range(1, 7):
        dp[1][j] = 1  # Base case: 1 way to roll each number
    
    for i in range(2, n + 1):
        for j in range(1, 7):
            for k in range(1, 7):
                if gcd(j, k) == 1:  # GCD condition
                    dp[i][j] = (dp[i][j] + dp[i - 1][k]) % MOD
            if i > 2:
                for k in range(1, 7):
                    dp[i][j] = (dp[i][j] - dp[i - 2][j] + MOD) % MOD  # Gap condition
    
    return sum(dp[n]) % MOD
← Back to All Questions