Add solution #2318

JoshCrozier · JoshCrozier · commit 6858100e893c · 2025-05-19T19:08:43.000-05:00
diff --git a/README.md b/README.md
@@ -1,4 +1,4 @@
-# 1,884 LeetCode solutions in JavaScript
+# 1,885 LeetCode solutions in JavaScript
 
 [https://leetcodejavascript.com](https://leetcodejavascript.com)
 
@@ -1760,6 +1760,7 @@
 2315|[Count Asterisks](./solutions/2315-count-asterisks.js)|Easy|
 2316|[Count Unreachable Pairs of Nodes in an Undirected Graph](./solutions/2316-count-unreachable-pairs-of-nodes-in-an-undirected-graph.js)|Medium|
 2317|[Maximum XOR After Operations](./solutions/2317-maximum-xor-after-operations.js)|Medium|
+2318|[Number of Distinct Roll Sequences](./solutions/2318-number-of-distinct-roll-sequences.js)|Hard|
 2319|[Check if Matrix Is X-Matrix](./solutions/2319-check-if-matrix-is-x-matrix.js)|Easy|
 2320|[Count Number of Ways to Place Houses](./solutions/2320-count-number-of-ways-to-place-houses.js)|Medium|
 2336|[Smallest Number in Infinite Set](./solutions/2336-smallest-number-in-infinite-set.js)|Medium|
diff --git a/solutions/2318-number-of-distinct-roll-sequences.js b/solutions/2318-number-of-distinct-roll-sequences.js
@@ -0,0 +1,55 @@
+/**
+ * 2318. Number of Distinct Roll Sequences
+ * https://leetcode.com/problems/number-of-distinct-roll-sequences/
+ * Difficulty: Hard
+ *
+ * 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.
+ */
+
+/**
+ * @param {number} n
+ * @return {number}
+ */
+var distinctSequences = function(n) {
+  const MOD = 1e9 + 7;
+  const gcd = (a, b) => b === 0 ? a : gcd(b, a % b);
+
+  const dp = new Array(n + 1)
+    .fill()
+    .map(() => new Array(7).fill().map(() => new Array(7).fill(0)));
+
+  for (let i = 1; i <= 6; i++) {
+    dp[1][i][0] = 1;
+  }
+
+  for (let len = 2; len <= n; len++) {
+    for (let curr = 1; curr <= 6; curr++) {
+      for (let prev = 0; prev <= 6; prev++) {
+        for (let prevPrev = 0; prevPrev <= 6; prevPrev++) {
+          if (dp[len - 1][prev][prevPrev] === 0) continue;
+          if (curr === prev || curr === prevPrev) continue;
+          if (prev !== 0 && gcd(curr, prev) !== 1) continue;
+          dp[len][curr][prev] = (dp[len][curr][prev] + dp[len - 1][prev][prevPrev]) % MOD;
+        }
+      }
+    }
+  }
+
+  let result = 0;
+  for (let curr = 1; curr <= 6; curr++) {
+    for (let prev = 0; prev <= 6; prev++) {
+      result = (result + dp[n][curr][prev]) % MOD;
+    }
+  }
+
+  return result;
+};
