Scale Engineer

Number of Distinct Roll Sequences

Hard
#2112Time: O(n * 7 * 7 * 6) = O(n). There are O(n) states, and each state's computation involves a loop of size 6.Space: O(n * 7 * 7) = O(n). This is for the memoization table. The recursion stack also contributes O(n) space in the worst case.1 company
Patterns
Dynamic ProgrammingMemoization
Companies
ServiceNow

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This problem exhibits optimal substructure and overlapping subproblems, making it a good candidate for dynamic programming. A straightforward way to implement a DP solution is using recursion with memoization (a top-down DP approach). We define a recursive function that calculates the number of valid sequences from a given state, and we store the results of subproblems in a memoization table to avoid recomputing them.

Algorithm

  • The state of our recursive function can be defined by solve(index, prev_roll, prev_prev_roll), which calculates the number of ways to complete a valid sequence from the current index given the two preceding rolls.
  • We use a 3D array, memo[n][7][7], to store the computed results for each state to avoid redundant calculations.
  • Base Case: When index == n, it means we have successfully constructed a valid sequence of length n. We return 1.
  • Recursive Step: For the current index, we iterate through all possible die rolls (curr from 1 to 6). For each curr, we check if it's a valid next roll:
    1. gcd(curr, prev_roll) == 1 (if prev_roll exists).
    2. curr != prev_roll and curr != prev_prev_roll (to satisfy the gap constraint).
  • If curr is valid, we make a recursive call solve(index + 1, curr, prev_roll) and add its result to our total count (modulo 10^9 + 7).
  • The result for the state (index, prev_roll, prev_prev_roll) is stored in the memoization table before being returned.
  • The process is initiated by calling solve(0, 0, 0, n), where 0 is a placeholder for non-existent rolls.

Walkthrough

The state of our recursive function can be defined by (index, prev_roll, prev_prev_roll), representing the number of ways to complete a valid sequence from the current index given the two preceding rolls.

  • index: The current roll position we are trying to fill (from 0 to n-1).
  • prev_roll: The value of the roll at index-1.
  • prev_prev_roll: The value of the roll at index-2.

We use a 3D array, memo[n][7][7], to store the computed results. The dimension size 7 is used to handle dummy values (like 0) for non-existent previous rolls at the beginning of the sequence.

The function works as follows:

  • Base Case: When index == n, it means we have successfully constructed a valid sequence of length n. We return 1.
  • Recursive Step: For the current index, we iterate through all possible die rolls (1 to 6). For each potential roll curr, we check if it's valid with respect to prev_roll and prev_prev_roll. If curr is a valid roll, we make a recursive call solve(index + 1, curr, prev_roll) and add its result to our total count. The final count for the state (index, prev_roll, prev_prev_roll) is stored in the memoization table before being returned.
class Solution {    int MOD = 1_000_000_007;    int[][][] memo;    int[][] gcd_cache;     private int gcd(int a, int b) {        if (gcd_cache[a][b] != 0) return gcd_cache[a][b];        int result = b == 0 ? a : gcd(b, a % b);        return gcd_cache[a][b] = gcd_cache[b][a] = result;    }     public int distinctSequences(int n) {        memo = new int[n + 1][7][7];        gcd_cache = new int[7][7];        for (int i = 0; i <= n; i++) {            for (int j = 0; j <= 6; j++) {                Arrays.fill(memo[i][j], -1);            }        }        return solve(0, 0, 0, n);    }     private int solve(int index, int prev1, int prev2, int n) {        if (index == n) {            return 1;        }        if (memo[index][prev1][prev2] != -1) {            return memo[index][prev1][prev2];        }         long count = 0;        for (int curr = 1; curr <= 6; curr++) {            if (curr == prev1 || curr == prev2) {                continue;            }            if (prev1 != 0 && gcd(curr, prev1) != 1) {                continue;            }            count = (count + solve(index + 1, curr, prev1, n)) % MOD;        }         return memo[index][prev1][prev2] = (int) count;    }}

Complexity

Time

O(n * 7 * 7 * 6) = O(n). There are O(n) states, and each state's computation involves a loop of size 6.

Space

O(n * 7 * 7) = O(n). This is for the memoization table. The recursion stack also contributes O(n) space in the worst case.

Trade-offs

Pros

  • Conceptually simpler to derive from the problem's recursive nature.

  • Correctly solves the problem within the given constraints.

Cons

  • Higher space complexity compared to the optimized iterative approach due to the memoization table.

  • May lead to a StackOverflowError for very large n (though n=10^4 is usually acceptable in modern environments).

  • Recursive function calls introduce some performance overhead.

Solutions

class Solution {public  int distinctSequences(int n) {    if (n == 1) {      return 6;    }    int mod = (int)1 e9 + 7;    int[][][] dp = new int[n + 1][6][6];    for (int i = 0; i < 6; ++i) {      for (int j = 0; j < 6; ++j) {        if (gcd(i + 1, j + 1) == 1 && i != j) {          dp[2][i][j] = 1;        }      }    }    for (int k = 3; k <= n; ++k) {      for (int i = 0; i < 6; ++i) {        for (int j = 0; j < 6; ++j) {          if (gcd(i + 1, j + 1) == 1 && i != j) {            for (int h = 0; h < 6; ++h) {              if (gcd(h + 1, i + 1) == 1 && h != i && h != j) {                dp[k][i][j] = (dp[k][i][j] + dp[k - 1][h][i]) % mod;              }            }          }        }      }    }    int ans = 0;    for (int i = 0; i < 6; ++i) {      for (int j = 0; j < 6; ++j) {        ans = (ans + dp[n][i][j]) % mod;      }    }    return ans;  }private  int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem