Number of Distinct Roll Sequences - Practice Coding Problems

Number of Distinct Roll Sequences - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: n = 4

› Output: 184

💡 Note: For 4 dice rolls, there are 184 valid sequences satisfying both constraints: adjacent dice must have GCD=1 and same values must be separated by more than 2 positions.

Example 2 — Minimum Case

$ Input: n = 2

› Output: 22

💡 Note: For 2 dice rolls, we need GCD(first, second) = 1. Valid pairs: (1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (2,1), (2,3), (2,5), (3,1), (3,2), (3,4), (3,5), (4,1), (4,3), (4,5), (5,1), (5,2), (5,3), (5,4), (5,6), (6,1), (6,5) = 22 total

Example 3 — Edge Case

$ Input: n = 1

› Output: 6

💡 Note: With only 1 dice roll, any value 1-6 is valid since there are no adjacent values or gap constraints to check.

Constraints

1 ≤ n ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

n = 4 dice rolls to make

Constraints

GCD(adjacent) = 1, gap > 2 for same values

Count

Find all valid sequences modulo 10^9+7

Key Takeaway

🎯 Key Insight: Use DP to track (position, last_roll, second_last_roll) states efficiently

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is to use dynamic programming with state (position, previous_roll, second_previous_roll) to track constraints. Best approach is memoized recursion or bottom-up DP. Time: O(n × 6²), Space: O(n × 6²)

Common Approaches

Approach	Time	Space	Notes
✓ Bottom-Up Dynamic Programming	O(n × 6³)	O(n × 6²)	Build solution iteratively using 3D DP table
Brute Force Recursion	O(6ⁿ)	O(n)	Generate all possible sequences and validate constraints
Memoized Recursion	O(n × 6²)	O(n × 6²)	Cache results for (position, prev_roll, prev2_roll) states

Bottom-Up Dynamic Programming — Algorithm Steps

Create 3D DP table dp[n+1][7][7]
Initialize base case: dp[n][*][*] = 1
Fill table backwards from position n-1 to 0
For each state, try all valid dice values
Return dp[0][0][0] (using 0 as placeholder for -1)

Visualization

Tap to expand

Step-by-Step Walkthrough

Base Case

dp[n][*][*] = 1 (end of sequence)

Fill Backwards

Compute dp[pos][prev][prev2] from dp[pos+1]

Try All Dice

Sum valid transitions for each state

Final Answer

dp[0][0][0] contains total count

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>

const int MOD = 1000000007;

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int solution(int n) {
    // dp[pos][prev][prev2] where prev/prev2 are 0-6 (0 means no previous roll)
    int dp[n + 1][7][7];
    
    // Base case: reached end of sequence
    for (int i = 0; i < 7; i++) {
        for (int j = 0; j < 7; j++) {
            dp[n][i][j] = 1;
        }
    }
    
    // Fill DP table backwards
    for (int pos = n - 1; pos >= 0; pos--) {
        for (int prev = 0; prev < 7; prev++) {
            for (int prev2 = 0; prev2 < 7; prev2++) {
                long long count = 0;
                for (int dice = 1; dice <= 6; dice++) {
                    // Check GCD constraint
                    if (prev > 0 && gcd(dice, prev) != 1) {
                        continue;
                    }
                    // Check gap constraint
                    if (prev2 > 0 && dice == prev2) {
                        continue;
                    }
                    
                    count = (count + dp[pos + 1][dice][prev]) % MOD;
                }
                
                dp[pos][prev][prev2] = count;
            }
        }
    }
    
    return dp[0][0][0];
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", solution(n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × 6³)

Three nested loops: n positions × 6 prev values × 6 prev2 values × 6 dice options

✓ Linear Growth

Space Complexity

O(n × 6²)

3D DP table of size n × 7 × 7 (including placeholder for -1)

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~35 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Bottom-Up Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler