The Number of Distinct Roll Sequences problem asks you to count distinct sequences of n dice rolls where: (1) each consecutive pair of rolls must be coprime (GCD=1), and (2) no value is repeated on two consecutive rolls. Return the count modulo 10^9+7. This hard coding problem uses memoized DP with the previous roll and second-previous roll as state.
ServiceNow asks this hard problem to test multi-state DP with coprimality constraints. The constraint "consecutive rolls must be coprime and different" creates a directed graph of valid transitions, and counting paths of length n requires DP over (last roll, second-last roll) states. The memoization and dynamic programming interview pattern is directly demonstrated.
Memoized DP with (last, secondLast) state. dp[i][last][secondLast] = number of valid sequences of length i ending with last preceded by secondLast. For each new roll value v (1 to 6): check gcd(v, last) == 1 and v != secondLast. Sum valid extensions. Use memoization on (i, last, secondLast) to avoid recomputation.
n=4 dice (1 to 6). Count sequences where each adjacent pair has GCD=1 and aren't the same. Valid transitions from 1: can go to 2,3,4,5,6 (1 is coprime with all). From 2: can go to 1,3,5 (odd primes + 1). From 4: can go to 1,3,5 (odd, coprime with 4). Enumerate all n=4 length paths = 184 (example answer, varies by n).
Multi-constraint sequence counting DPs need sufficient state to capture all constraints. Here, "no repeat in consecutive rolls" and "consecutive coprimality" both require the last two values as state. When you see "count sequences satisfying pairwise constraints," design your DP state to include all values that the constraint references. Precompute a coprimality table for 1-6 to avoid repeated GCD calculations. Practice similar "count paths with local constraints" DP problems.
