aboutsummaryrefslogtreecommitdiff
path: root/count_hidden_sequences.c
blob: 0d8c2e155ed679738face38cbb1ffecb8f5451f1 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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
}