Number of Distinct Roll Sequences

Hard

ServiceNow

2 views

Topics:

Dynamic Programming

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 2 rolls between equal valued rolls. More formally, if the value of the i^th roll is equal to the value of the j^th roll, then abs(i - j) > 2.

Return the total number of distinct sequences possible. Since the answer may be very large, return it modulo 10⁹ + 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 <= 10⁴

Try coding it in LeetCode

Number of Distinct Roll Sequences

Hard

ServiceNow

2 views

Topics:

Dynamic Programming

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 2 rolls between equal valued rolls. More formally, if the value of the i^th roll is equal to the value of the j^th roll, then abs(i - j) > 2.

Return the total number of distinct sequences possible. Since the answer may be very large, return it modulo 10⁹ + 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 <= 10⁴

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum possible value of `n` (the number of dice rolls)?
Should I handle any edge cases, such as when `n` is 0 or 1?
Is the modulo operation (10^9 + 7) only for the final result, or should I apply it during intermediate calculations to prevent overflow?
Could you clarify the definition of 'distinct roll sequences' further with an example, specifically highlighting the GCD = 1 rule?
Are there any specific performance considerations or constraints given the potential range of `n`?

Brute Force Solution

Approach

The goal is to find the total count of unique dice roll sequences of a given length. The brute force solution tries every possible combination of dice rolls to find the valid sequences.

Here's how the algorithm would work step-by-step:

Consider each possible dice roll as a single choice, starting with the first roll.
For each possible value on the first roll, consider every possible value for the second roll, and then every possible value for the third roll, and so on until the sequence reaches the desired length.
While creating these sequences, check if any adjacent rolls are the same, or if any sequence has more than a specific number of the same dice roll value.
If a sequence violates the rules, discard it and try the next one.
If a sequence satisfies all the conditions, count it as a valid sequence.
Repeat this process of generating and checking until all possible combinations of dice rolls have been explored.
Finally, report the total number of valid dice roll sequences found.

Code Implementation

def number_of_distinct_roll_sequences_brute_force(number_of_rolls, max_face, max_repeats):
    valid_sequences_count = 0

    def is_valid_sequence(sequence):
        if len(sequence) < 2:
            return True

        # Check for adjacent identical rolls
        for index in range(len(sequence) - 1):
            if sequence[index] == sequence[index + 1]:
                return False

        # Check for excessive repetition of any single roll
        for face_value in range(1, max_face + 1):
            face_count = sequence.count(face_value)
            if face_count > max_repeats:
                return False

        return True

    def generate_sequences(current_sequence):
        nonlocal valid_sequences_count

        if len(current_sequence) == number_of_rolls:
            # A full sequence is generated. Check if it is valid and update the count.
            if is_valid_sequence(current_sequence):
                valid_sequences_count += 1
            return

        # Try each face value for the next roll.
        for face_value in range(1, max_face + 1):
            generate_sequences(current_sequence + (face_value,))

    # Initiate with an empty sequence
    generate_sequences(tuple())
    return valid_sequences_count

Big(O) Analysis

Time Complexity

O(6^n) – The brute force approach explores all possible dice roll sequences of length n. For each position in the sequence, there are 6 possible dice roll values. Thus, the total number of possible sequences is 6 * 6 * ... * 6 (n times), which equals 6^n. The algorithm checks each of these sequences for validity, leading to a time complexity that is directly proportional to the number of sequences it generates. Therefore, the time complexity is O(6^n).

Space Complexity

O(N) – The brute force solution described relies heavily on recursive calls to explore all possible dice roll sequences. In the worst-case scenario, the depth of the recursion can reach N, where N is the desired length of the dice roll sequence. Each recursive call adds a new frame to the call stack, storing function arguments and local variables. Therefore, the auxiliary space complexity is proportional to the maximum depth of the recursion, which is O(N).

Optimal Solution

Approach

The best way to solve this is to break the big problem into smaller, overlapping subproblems. We remember the solutions to these smaller problems so we don't have to calculate them again, saving a lot of time.

Here's how the algorithm would work step-by-step:

Imagine we're building roll sequences one roll at a time. Each time we roll, we want to know how many different *complete* sequences we can make from *that point onward*.
We'll use a 'memory' to store the answer to 'how many sequences can I make if I'm currently at roll X, with the last roll being Y' so we don't have to recalculate it multiple times.
When we make a new roll, we can only pick numbers that aren't the same as the last roll, or the roll before that. This makes sure we avoid those immediate repeats.
Also, we need to make sure that no more than two adjacent rolls can be the same in a row. This is another condition we need to follow when choosing our rolls.
If we reach the desired number of rolls, then we've found one complete sequence!
We add up the number of complete sequences we can make from each possible next roll to get our final total. By remembering these totals along the way, we avoid repeating calculations, making it efficient.

Code Implementation

def number_distinct_roll_sequences(number_of_rolls, face_count):
    modulo = 10**9 + 7

    # dp[i][j][k] stores the number of distinct sequences
    # of length i ending with j, with the previous roll being k
    dp = [[[0] * (face_count + 1) for _ in range(face_count + 1)]
          for _ in range(number_of_rolls + 1)]

    # Initialize base cases for sequences of length 1
    for face_value in range(1, face_count + 1):
        dp[1][face_value][0] = 1

    for roll_index in range(2, number_of_rolls + 1):
        for current_roll in range(1, face_count + 1):
            for previous_roll in range(1, face_count + 1):
                # Avoid immediate repeats
                if current_roll != previous_roll:
                    for second_previous_roll in range(face_count + 1):
                        # Here's the core logic.
                        # Only consider valid transitions.
                        if current_roll != second_previous_roll:
                            dp[roll_index][current_roll][previous_roll] = \
                                (dp[roll_index][current_roll][previous_roll] + \
                                 dp[roll_index - 1][previous_roll][second_previous_roll]) % modulo

    total_sequences = 0

    # Sum up all possible sequences ending at the last roll.
    for last_roll in range(1, face_count + 1):
        for previous_roll in range(face_count + 1):
            total_sequences = (total_sequences + dp[number_of_rolls][last_roll][previous_roll]) % modulo

    return total_sequences

Big(O) Analysis

Time Complexity

O(n) – The algorithm uses dynamic programming to build roll sequences one roll at a time up to n rolls. The core of the algorithm involves iterating through possible next rolls (1 to 6) for each current roll, while maintaining a memory of already computed subproblems to avoid recomputation. The size of the dynamic programming table (memory) is proportional to n, representing the number of rolls, since for each roll we consider a fixed number of possibilities for the previous roll, and the roll before that. The calculations to populate each entry in the DP table take constant time because they involve checking a fixed number of conditions and combining previous results. Thus, the overall time complexity is O(n).

Space Complexity

O(N) – The solution uses dynamic programming with memoization to store the number of distinct roll sequences. The 'memory' described corresponds to a 3D array (or equivalent data structure) used to store intermediate results. The dimensions of this data structure are determined by the number of rolls (N), the possible values of the last roll (up to 6), and the possible values of the second to last roll (up to 6). Therefore, the space complexity is proportional to N * 6 * 6, which simplifies to O(N).

Edge Cases

Case	How to Handle
n = 0 (no dice rolls)	Return 1, as there's one way to roll no dice.
n = 1 (single dice roll)	Return 6, as there are six possible outcomes for the first roll.
Large n (e.g., n near the maximum integer value)	Use dynamic programming with memoization to avoid redundant calculations and manage the exponential growth of possibilities within memory limits and consider integer overflow using modulo operator.
Consecutive rolls resulting in GCD > 1 (e.g., 2 and 4)	Ensure the GCD check is implemented correctly, and the transitions in dynamic programming only consider valid roll pairs.
Consecutive rolls resulting in the same number (e.g., 1 and 1)	Ensure that the transition function skips the cases where two consecutive rolls are the same.
Integer overflow when calculating the number of sequences	Apply the modulo operator (10^9 + 7) after each arithmetic operation to prevent integer overflow.
Correctness of GCD calculation	Test the GCD function with various pairs of numbers to ensure its accuracy before using it in the main algorithm.
Time Limit Exceeded (TLE) for large values of n without memoization	Implement memoization in dynamic programming using a 2D array or hashmap to store the results of subproblems, avoiding redundant computations.