#2318
Number of Distinct Roll Sequences
expert · 1225 · lc hard +32 · verified · 58.2% accepted · 457 likes · top 54%
Description
You are given an integer n. Roll a fair 6-sided die n times. Count the distinct sequences satisfying both:
- The GCD of every pair of adjacent values equals 1.
- Equal values must be at least 3 positions apart: if rolls i and j are equal then abs(i - j) > 2.
Return the count modulo 109 + 7. Two sequences differ when at least one position has a different value.
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.
Code
1
2
3