<Codesignal> Three Split

Medium

You have a long strip of paper with integers written on it in a single line from left to right. You wish to cut the paper into exactly three pieces such that each piece contains at least one integer and the sum of the integers in each piece is the same. You cannot cut through a number, i.e. each initial number will unambiguously belong to one of the pieces after cutting. How many ways can you do it?

It is guaranteed that the sum of all elements in the array is divisible by 3.

Example

For a = [0, -1, 0, -1, 0, -1], the output should be
threeSplit(a) = 4.

Here are all possible ways:

• [0, -1] [0, -1] [0, -1]
• [0, -1] [0, -1, 0] [-1]
• [0, -1, 0] [-1, 0] [-1]
• [0, -1, 0] [-1] [0, -1]

Input/Output

• [execution time limit] 0.5 seconds (c)

• [input] array.integer a

  Guaranteed constraints:
  5 ≤ a.length ≤ 10^4,
  -10^8 ≤ a[i] ≤ 10^8.

• [output] integer

  • It's guaranteed that for the given test cases the answer always fits signed 32-bit integer type.

[C] Syntax Tips

// Prints help message to the console
// Returns a string
char * helloWorld(char * name) {
    char * answer = malloc(strlen(name) + 8);
    printf("This prints to the console when you Run Tests");
    strcpy(answer, "Hello, ");
    strcat(answer, name);
    return answer;
}

---

Solution

// Arrays are already defined with this interface:
// typedef struct arr_##name {
//   int size;
//   type *arr;
// } arr_##name;
//
// arr_##name alloc_arr_##name(int len) {
//   arr_##name a = {len, len > 0 ? malloc(sizeof(type) * len) : NULL};
//   return a;
// }
//
//
int threeSplit(arr_integer a)
{
	long int sum=0, sum1=0, count=0;

	for(int i=0;i<a.size;i++)
		sum+=a.arr[i];

	for(int i=0;i<a.size-2;i++)
	{
		long int sum2=0;
		sum1+=a.arr[i];
		if(sum1!=sum/3)
			continue;
		for(int j=i+1;j<a.size-1;j++)
		{
			sum2+=a.arr[j];
			if(sum1!=sum2)
				continue;

			count+=sum==sum1+2*sum2;
		}
	}

	return count;    
}