Hi,
Here is my simple Prefix sum based java program
public int solve(List A) {
if (A == null || A.size() == 0) {
return 0;
}
int output = 0;
int size = A.size();
int[] oddSum = new int[size];
int[] evenSum = new int[size];
for (int i = 0; i < size; i++) {
if (i % 2 == 0) {
evenSum[i] = A.get(i) + (i > 0 ? evenSum[i-1] : 0);
oddSum[i] = (i > 0) ? oddSum[i-1] : 0;
} else {
oddSum[i] = A.get(i) + (i > 0 ? oddSum[i-1] : 0);
evenSum[i] = (i > 0) ? evenSum[i-1] : 0;
}
}
// Arrays.stream(oddSum).forEach(a -> System.out.print(a + ", "));
// System.out.println();
// Arrays.stream(evenSum).forEach(a -> System.out.print(a + ", "));
// System.out.println();
for (int i = 0; i < size; i++) {
int oSum = 0;
int eSum = 0;
oSum += (i > 0) ? oddSum[i-1] : 0;
oSum += (i < size - 1) ? (evenSum[size-1] - evenSum[i]) : 0;
eSum += (i > 0)? evenSum[i-1] : 0;
eSum += (i < size - 1) ? (oddSum[size - 1] - oddSum[i]) : 0;
// System.out.println("i = " + i + " oSum = "+ oSum + " eSum = " + eSum);
if (oSum == eSum) {
output ++;
}
}
return output;
}