aboutsummaryrefslogtreecommitdiff
path: root/split_array.c
blob: d0f06839705498852d6c12b1ed0cd2c1dd2aed00 (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
30
31
32
33
34
35
// 2270. Number of Ways to Split Array
#include <stdio.h>
#include <stdlib.h>

/*
 * given a 0-indexed integer array 'nums' of length 'n'. 'nums' contains a valid
 * split at index 'i' if the following are true:
 * - the sum of the first 'i + 1' elements is greater than or equal to the sum
 * of the last 'n - i - 1' elements
 * - there is at least one element to the right of 'i'. that is, 0 <= i < n - 1
 * return the number of valid splits in 'nums'
 */

int waysToSplitArray(int *nums, int nums_size) {
  int n = nums_size, ans = 0;
  long long *presum = malloc(n * sizeof(long long));
  presum[0] = nums[0];
  for (int i = 1; i < n; i++)
    presum[i] = presum[i - 1] + nums[i];
  long long half = presum[n - 1] / 2;
  if (presum[n - 1] % 2)
    if (presum[n - 1])
      half++;
  for (int i = 0; i < n - 1; i++)
    if (presum[i] >= half)
      ans++;
  return ans;
}

int main() {
  int n1[] = {10, 4, -8, 7}, ns1 = 4;
  int n2[] = {2, 3, 1, 0}, ns2 = 4;
  printf("%d\n", waysToSplitArray(n1, ns1)); // expect: 2
  printf("%d\n", waysToSplitArray(n2, ns2)); // expect: 2
}