http://codechillout.sphere-contest.com/problems/onlineround/PREFSUFF
Prefix-suffix balance
One of the most popular problems presented during the initial stages of IT recruitment is that of finding a place in a sequence of integers which divides it into two groups of equal sum, i.e., at a position where the sum of the prefix is equal to the sum of the suffix. Your task is to find this position.
Input
The first line contains exactly one number t, representing the number of data sets. Each data set i is a single line, consisting of the sequence length mi and exactly mi integers which form the sequence. Numbers in data sets are separated by spaces.
Output
For each data set i print the shortest possible length of the prefix for which the sum of elements is equal to the sum of elements of the determined suffix. If desired number does not exist, then print 0. Answers for data sets should be separated by new lines.
Notes
The prefix and suffix cannot be empty.
Example
Input: 4 5 4 2 3 1 2 5 4 -2 1 1 -2 6 1 -1 1 -1 1 -1 3 0 0 0 Output: 2 0 2 1
Answer
#include
int main(void) {
int instances;
scanf("%d", &instances);
int n;
int i;
for(i = 0 ; i < instances ; i++){
scanf("%d", &n);
int entries[n];
int j;
for(j = 0 ; j < n ; j++){
scanf("%d", &entries[j]);
}
int sumA[n-1];
int total = 0;
int k;
int flag1 =1;
for(k = 0 ; k <= n-2 ; k++){
if(entries[k] != entries[n-(k)]) // Check for palindrome
flag1=0;
total +=entries[k];
sumA[k] = total;
}
if(flag1 == 1 && entries[n/2] == entries[(n/2)-1])
return (n/2)-1;
total +=entries[n-1];
int flag = 1;
if(total%2 == 0){ // If it is odd it cannot be split
int j;
int tot2 = total/2;
for(j = 0 ; j <= n-2 ; j++){
if(sumA[j] == tot2){
printf("%d\n", j+1);
flag = 0;
break;
}
}
}
if(flag ==1)
printf("0\n");
}
return 0;
}