2318. Number of Distinct Roll Sequences LeetCode Solution

In this guide, you will get 2318. Number of Distinct Roll Sequences LeetCode Solution with the best time and space complexity. The solution to Number of Distinct Roll Sequences problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Number of Distinct Roll Sequences solution in C++
4. Number of Distinct Roll Sequences solution in Java
5. Number of Distinct Roll Sequences solution in Python
6. Additional Resources

Problem Statement of Number of Distinct Roll Sequences

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 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

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

2318. Number of Distinct Roll Sequences LeetCode Solution in C++

class Solution {
 public:
  int distinctSequences(int n) {
    vector<vector<vector<int>>> mem(n + 1,
                                    vector<vector<int>>(7, vector<int>(7)));
    return distinctSequences(n, 0, 0, mem);
  }

 private:
  static constexpr int kMod = 1'000'000'007;

  // Returns the number of distinct sequences for n dices with `prev` and
  // `prevPrev`.
  int distinctSequences(int n, int prev, int prevPrev,
                        vector<vector<vector<int>>>& mem) {
    if (n == 0)
      return 1;
    if (mem[n][prev][prevPrev] > 0)
      return mem[n][prev][prevPrev];

    for (int dice = 1; dice <= 6; ++dice)
      if (dice != prev && dice != prevPrev &&
          (prev == 0 || gcd(dice, prev) == 1)) {
        mem[n][prev][prevPrev] += distinctSequences(n - 1, dice, prev, mem);
        mem[n][prev][prevPrev] %= kMod;
      }

    return mem[n][prev][prevPrev];
  }
};
/* code provided by PROGIEZ */

2318. Number of Distinct Roll Sequences LeetCode Solution in Java

class Solution {
  public int distinctSequences(int n) {
    int[][][] mem = new int[n + 1][7][7];
    return distinctSequences(n, 0, 0);
  }

  private static final int kMod = 1_000_000_007;

  // Returns the number of distinct sequences for n dices with `prev` and
  // `prevPrev`.
  private int distinctSequences(int n, int prev, int prevPrev, int[][][] mem) {
    if (n == 0)
      return 1;
    if (mem[n][prev][prevPrev] > 0)
      return mem[n][prev][prevPrev];

    for (int dice = 1; dice <= 6; ++dice)
      if (dice != prev && dice != prevPrev && (prev == 0 || gcd(dice, prev) == 1)) {
        mem[n][prev][prevPrev] += distinctSequences(n - 1, dice, prev, mem);
        mem[n][prev][prevPrev] %= kMod;
      }

    return mem[n][prev][prevPrev];
  }

  private int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
  }
}
// code provided by PROGIEZ

2318. Number of Distinct Roll Sequences LeetCode Solution in Python

class Solution:
  def distinctSequences(self, n: int) -> int:
    kMod = 1_000_000_007

    @functools.lru_cache(None)
    def dp(n: int, prev: int, prevPrev: int) -> int:
      """
      Returns the number of distinct sequences for n dices with `prev` and
      `prevPrev`.
      """
      if n == 0:
        return 1
      res = 0
      for dice in range(1, 7):
        if (dice not in (prev, prevPrev) and
                (prev == 0 or math.gcd(dice, prev) == 1)):
          res += dp(n - 1, dice, prev)
          res %= kMod
      return res

    return dp(n, 0, 0)
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.