TheRealSamuel/LeetCodeProblem
0564
1{2 "id": 2249,3 "name": "count_the_hidden_sequences",4 "difficulty": "Medium",5 "link": "https://leetcode.com/problems/count-the-hidden-sequences/",6 "date": "1641600000000",7 "task_description": "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)`. More formally, call the hidden sequence `hidden`, then we have that `differences[i] = hidden[i + 1] - hidden[i]`. You are further given two integers `lower` and `upper` that describe the **inclusive** range of values `[lower, upper]` that the hidden sequence can contain. For example, given `differences = [1, -3, 4]`, `lower = 1`, `upper = 6`, the hidden sequence is a sequence of length `4` whose elements are in between `1` and `6` (**inclusive**). `[3, 4, 1, 5]` and `[4, 5, 2, 6]` are possible hidden sequences. `[5, 6, 3, 7]` is not possible since it contains an element greater than `6`. `[1, 2, 3, 4]` is not possible since the differences are not correct. Return _the number of **possible** hidden sequences there are._ If there are no possible sequences, return `0`. **Example 1:** ``` **Input:** differences = [1,-3,4], lower = 1, upper = 6 **Output:** 2 **Explanation:** The possible hidden sequences are: - [3, 4, 1, 5] - [4, 5, 2, 6] Thus, we return 2. ``` **Example 2:** ``` **Input:** differences = [3,-4,5,1,-2], lower = -4, upper = 5 **Output:** 4 **Explanation:** The possible hidden sequences are: - [-3, 0, -4, 1, 2, 0] - [-2, 1, -3, 2, 3, 1] - [-1, 2, -2, 3, 4, 2] - [0, 3, -1, 4, 5, 3] Thus, we return 4. ``` **Example 3:** ``` **Input:** differences = [4,-7,2], lower = 3, upper = 6 **Output:** 0 **Explanation:** There are no possible hidden sequences. Thus, we return 0. ``` **Constraints:** `n == differences.length` `1 <= n <= 105` `-105 <= differences[i] <= 105` `-105 <= lower <= upper <= 105`",8 "public_test_cases": [9 {10 "label": "Example 1",11 "input": "differences = [1,-3,4], lower = 1, upper = 6",12 "output": "2 "13 },14 {15 "label": "Example 2",16 "input": "differences = [3,-4,5,1,-2], lower = -4, upper = 5",17 "output": "4 "18 },19 {20 "label": "Example 3",21 "input": "differences = [4,-7,2], lower = 3, upper = 6",22 "output": "0 "23 }24 ],25 "private_test_cases": [26 {27 "input": [28 [29 -70,30 69,31 86,32 -85,33 96,34 4,35 52,36 48,37 51,38 -86,39 71,40 -28,41 41,42 16,43 -45,44 -53,45 73,46 47,47 -27,48 33,49 -50,50 -17,51 -73,52 87,53 -54,54 -17,55 17,56 -100,57 101,58 98,59 -6,60 22,61 -69,62 -97,63 -89,64 100,65 -2,66 40,67 60,68 99,69 16,70 22,71 -105,72 -27,73 18,74 -32,75 -95,76 89,77 85,78 -67,79 -41,80 -33,81 -7,82 10083 ],84 5,85 10086 ],87 "output": 088 },89 {90 "input": [91 [92 27,93 -28,94 -37,95 -47,96 -3,97 90,98 -46,99 37,100 -17,101 -14,102 -85,103 90,104 -53,105 16,106 17,107 17,108 52,109 43,110 -89,111 84,112 70,113 2,114 -29,115 59,116 -70,117 103,118 86,119 58,120 82,121 17,122 -48,123 -18124 ],125 25,126 53127 ],128 "output": 0129 },130 {131 "input": [132 [133 -13,134 58,135 84,136 -26,137 99,138 -26,139 6,140 26,141 -55,142 -70,143 -57,144 52,145 72,146 -98,147 28,148 -99,149 70,150 99,151 -23,152 85,153 78,154 64,155 26,156 89,157 -42,158 67,159 -93,160 56,161 79,162 43,163 49,164 44,165 -1,166 60,167 -15,168 45,169 -88,170 -80,171 25,172 -78,173 79,174 53,175 -71,176 -62,177 -44,178 -89,179 28,180 -36,181 -82,182 -104,183 -50,184 46,185 -47,186 25,187 -50,188 -42,189 -45,190 -76,191 20192 ],193 -92,194 -4195 ],196 "output": 0197 },198 {199 "input": [200 [201 -77,202 -59,203 -90,204 -45,205 20,206 -72,207 -68,208 1,209 -103,210 -11,211 -47,212 93,213 -10,214 -86,215 -94,216 76,217 73218 ],219 -37,220 48221 ],222 "output": 0223 },224 {225 "input": [226 [227 -105,228 -74,229 -7,230 68,231 -101,232 -8,233 49,234 10,235 26,236 -83,237 70,238 94,239 60,240 66,241 81,242 98,243 2,244 65,245 -69,246 -21,247 -58,248 -42,249 87,250 -29,251 78,252 -94,253 -41,254 36,255 -34,256 75,257 94,258 55,259 -20,260 -38,261 -66,262 33,263 105,264 54,265 26,266 78,267 -101,268 10,269 -31,270 73,271 19,272 -81,273 67,274 -32,275 -11,276 -72,277 -24,278 34,279 -77,280 53,281 -74,282 50,283 64,284 -62,285 -71,286 54,287 54,288 -59,289 -9,290 -21,291 100,292 -81,293 66294 ],295 105,296 105297 ],298 "output": 0299 },300 {301 "input": [302 [303 61,304 33,305 -22,306 34,307 13,308 -75,309 -53,310 90,311 -9,312 79,313 55,314 -5,315 6,316 55,317 10,318 -53,319 -104,320 -82,321 92,322 46,323 -54,324 -34,325 85,326 96,327 -102,328 -28,329 -55,330 -60,331 19,332 10,333 54,334 -63,335 -6,336 14,337 -80,338 61,339 -50,340 43341 ],342 -71,343 76344 ],345 "output": 0346 },347 {348 "input": [349 [350 69,351 -12,352 -9,353 78,354 -50,355 18,356 -5,357 -28,358 90,359 26,360 -60,361 40,362 -1,363 -95,364 -51,365 99,366 64,367 -23,368 -93,369 6,370 -104,371 -80,372 26,373 81,374 -103,375 56,376 -43,377 86,378 66,379 29,380 -24,381 -86,382 -77,383 12,384 -36,385 -71,386 96,387 10,388 -41,389 -26,390 72,391 32,392 -35,393 99,394 -87395 ],396 96,397 104398 ],399 "output": 0400 },401 {402 "input": [403 [404 6,405 -21,406 46,407 90,408 -56,409 -35,410 -91,411 73,412 -71,413 23,414 35,415 43,416 -13,417 -33,418 70,419 -92,420 47,421 6,422 32,423 -18,424 71,425 20,426 12,427 -78,428 40,429 -55,430 -29,431 48,432 45,433 9,434 -83,435 -83,436 48,437 -52,438 -98,439 51,440 17,441 -28,442 -53,443 46,444 -11,445 -42,446 -83,447 -104,448 -51,449 -88,450 26451 ],452 -102,453 -72454 ],455 "output": 0456 },457 {458 "input": [459 [460 53,461 -57,462 -25,463 29,464 97,465 70,466 -62,467 25,468 76,469 -58,470 0,471 67,472 -9,473 53,474 -37475 ],476 -65,477 -47478 ],479 "output": 0480 },481 {482 "input": [483 [484 -7,485 60,486 -76,487 -77,488 -45,489 17,490 -11,491 8,492 -78,493 -52,494 13,495 33,496 43,497 -90,498 61,499 -77,500 -80,501 -32,502 102,503 -34,504 -33,505 -71,506 -6,507 -71,508 7,509 59,510 -93,511 60,512 74,513 -53,514 -96,515 7,516 43,517 -24,518 -76,519 72,520 -53,521 -64,522 23,523 74,524 -18,525 -7,526 24,527 25,528 -20,529 -70,530 17,531 90,532 -46,533 12,534 -103,535 -67,536 -9,537 83,538 -20,539 37,540 22,541 53,542 -90,543 87,544 55,545 -42,546 -60,547 -94,548 -45,549 -23,550 -50,551 91,552 71,553 -24,554 -32,555 -94,556 100,557 -50,558 -47,559 32,560 46,561 -11,562 102,563 42,564 -53,565 58566 ],567 39,568 62569 ],570 "output": 0571 }572 ],573 "haskell_template": "numberOfArrays :: [Int] -> Int -> Int -> Int\nnumberOfArrays differences lower upper ",574 "ocaml_template": "let numberOfArrays (differences: int list) (lower: int) (upper: int) : int = ",575 "scala_template": "def numberOfArrays(differences: List[Int],lower: Int,upper: Int): Int = { \n \n}",576 "java_template": "public static int numberOfArrays(List<Integer> differences, int lower, int upper) {\n\n}",577 "python_template": "class Solution(object):\n def numberOfArrays(self, differences, lower, upper):\n \"\"\"\n :type differences: List[int]\n :type lower: int\n :type upper: int\n :rtype: int\n \"\"\"\n "578}