aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-04-20 19:06:52 -0600
committerJack Sangdahl <[email protected]>2025-04-20 19:06:52 -0600
commitebb9933e94bf1beacf487b8a3f1915a0ba92edbc (patch)
treea10aa39ee832311cb20d60989934129b8c529456
parentfef03eaef98cc479f58c4e1dd4619db665f97e8f (diff)
downloadleetcode-ebb9933e94bf1beacf487b8a3f1915a0ba92edbc.tar.gz
leetcode-ebb9933e94bf1beacf487b8a3f1915a0ba92edbc.zip
2145. count the hidden sequences
-rw-r--r--count_hidden_sequences.c29
-rw-r--r--count_hidden_sequences.py30
2 files changed, 59 insertions, 0 deletions
diff --git a/count_hidden_sequences.c b/count_hidden_sequences.c
new file mode 100644
index 0000000..0d8c2e1
--- /dev/null
+++ b/count_hidden_sequences.c
@@ -0,0 +1,29 @@
+// 2145. Count the Hidden Sequences
+#include "leetcode.h"
+
+/*
+ * you are given a 0-indexed array of 'n' integers 'differences', which
+ * describes the differences between each pair of consecutive integers of a
+ * hidden sequence of length '(n + 1)'. you are further given two integers
+ * 'lower' and 'upper' that describe the inclusive range of values '[lower,
+ * upper]' that the hidden sequence can contain. return the number of possible
+ * hidden sequences there are. if there are no possible sequences, return 0.
+ */
+
+int numberOfArrays(int *differences, int differencesSize, int lower,
+ int upper) {
+ long long cnt = 0, a = 0, b = 0;
+ for (int i = 0; i < differencesSize; i++) {
+ cnt += differences[i];
+ a = fmax(a, cnt);
+ b = fmin(b, cnt);
+ }
+ return fmax(0L, (upper - lower) - (a - b) + 1);
+}
+
+int main() {
+ int d1[] = {1, -3, 4}, d2[] = {3, -4, 5, 1, -2}, d3[] = {4, -7, 2};
+ printf("%d\n", numberOfArrays(d1, ARRAY_SIZE(d1), 1, 6)); // expect: 2
+ printf("%d\n", numberOfArrays(d2, ARRAY_SIZE(d2), -4, 5)); // expect: 4
+ printf("%d\n", numberOfArrays(d3, ARRAY_SIZE(d3), 3, 6)); // expect: 0
+}
diff --git a/count_hidden_sequences.py b/count_hidden_sequences.py
new file mode 100644
index 0000000..c229f7a
--- /dev/null
+++ b/count_hidden_sequences.py
@@ -0,0 +1,30 @@
+# 2145. Count the Hidden Sequences
+from itertools import accumulate
+
+"""
+you are given a 0-indexed array of 'n' integers 'differences', which
+describes the differences between each pair of consecutive integers of a
+hidden sequence of length '(n + 1)'. you are further given two integers
+'lower' and 'upper' that describe the inclusive range of values '[lower,
+upper]' that the hidden sequence can contain. return the number of possible
+hidden sequences there are. if there are no possible sequences, return 0.
+"""
+
+
+class Solution(object):
+ def numberOfcntrrays(self, differences, lower, upper):
+ """
+ :type differences: List[int]
+ :type lower: int
+ :type upper: int
+ :rtype: int
+ """
+ cnt = list(accumulate(differences, initial=0))
+ return max(0, (upper - lower) - (max(cnt) - min(cnt)) + 1)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.numberOfcntrrays(differences=[1, -3, 4], lower=1, upper=6))
+ print(obj.numberOfcntrrays(differences=[3, -4, 5, 1, -2], lower=-4, upper=5))
+ print(obj.numberOfcntrrays(differences=[4, -7, 2], lower=3, upper=6))