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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Distinct Roll Sequences

Number: 2404

Difficulty: Hard

Paid? No

Companies: ServiceNow

Problem Description

You are given an integer n representing the number of times you roll a fair 6-sided dice. You need to count the number of distinct sequences of rolls such that:

  1. The greatest common divisor (gcd) of every pair of adjacent dice outcomes is 1.
  2. If two rolls have the same value, there must be at least a gap of 2 rolls between them (i.e., if the value of the i-th roll equals the j-th roll, then |i - j| > 2). Return the total number of valid sequences modulo 10^9 + 7.

Key Insights

  • The adjacent gcd condition implies that only pairs (a, b) where gcd(a, b) = 1 are allowed. Precomputing the valid transitions between dice values (1-6) is useful.
  • The gap restriction prevents immediate repetition with an intervening roll, effectively requiring tracking of at least the last two outcomes.
  • A dynamic programming (DP) strategy is ideal where the state includes information about the last one or two dice outcomes.
  • Since n can be as large as 10^4, it is important to design the DP to run in O(n) time (or with a small constant factor) and use space-optimization techniques.

Space and Time Complexity

Time Complexity: O(n) (with a small constant factor since we are iterating over a fixed set of dice faces and precomputed valid transitions) Space Complexity: O(1) when optimizing DP with a sliding window (only storing states for the last two rolls)

Solution

We use dynamic programming with a state that captures the last two outcomes. Let dp[i][prev1][prev2] represent the number of valid sequences of length i ending with "prev1" as the last roll and "prev2" as the roll before that (using a placeholder for sequences shorter than 2). When adding a new roll "newFace":

  • Ensure gcd(prev1, newFace) equals 1.
  • If prev2 equals newFace (and prev2 is not just a placeholder), the move is invalid because it violates the gap condition. A precomputed transition map for valid dice pairs (based on gcd) simplifies the update step. Finally, we sum over all valid end states after constructing sequences of length n and return the result modulo 10^9 + 7.

Code Solutions

Below are solutions in Python, JavaScript, C++, and Java.

MOD = 10**9 + 7

# Function to compute gcd
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def countSequences(n: int) -> int:
    if n == 0:
        return 0
    # Precompute valid transitions: for any dice face 'i', find all dice faces 'j' with gcd(i, j) == 1.
    valid_next = {i: [] for i in range(1, 7)}
    for i in range(1, 7):
        for j in range(1, 7):
            if gcd(i, j) == 1:
                valid_next[i].append(j)

    # dp holds states as key (last, second_last), using 0 as a placeholder when undefined.
    dp = {}
    # Base case: sequences of length 1 (no second_last roll).
    for face in range(1, 7):
        dp[(face, 0)] = 1

    # Build sequences from length 2 to n.
    for roll in range(2, n + 1):
        new_dp = {}
        for (last, second_last), count in dp.items():
            for new_face in valid_next[last]:
                # If second_last equals new_face (and second_last is valid), skip to enforce the gap condition.
                if second_last == new_face and second_last != 0:
                    continue
                state = (new_face, last)
                new_dp[state] = (new_dp.get(state, 0) + count) % MOD
        dp = new_dp

    return sum(dp.values()) % MOD

# Example usage:
print(countSequences(4))
← Back to All Questions