Quize - a Balanced Index

Wednesday 17 December 2008

Quize

Give an interger array A[N], P is a balanced index if
A + A + ... + A[P−1] = A[P+1] + ... + A[N−2] + A[N−1].

N is an integer within the range [0, 100,000];
Expected worst-case complexity is O(N);

Solution

I thought it's quite easy:
just scan the array from A to A[n] and add each vaule in an new array, then do it again in reverse order.

In 10 minutes, I submitted the answer:

``````class Quize {
public int findBalancedIndex(int[] A) {

/* arrary stores the vaule A, A+A, ... , A+A+A+...+A[N-1] */
int[] begin = new int[A.length];
/* arrary stores the vaule A+a+...+A[N-1], ... ,A[N-2]+A[N-1], A[N-1] */
int[] end = new int[A.length];

int sum = 0;
for (int i = 0; i < A.length; i++) {
sum += A[i];
begin [i] = sum;
}

sum = 0;
for (int j = A.length-1; j >= 0; j--) {
sum += A[j];
end [j] = sum;
}
/*case 1: 0 = A+A+...A[N-1]*/
if (end  == 0) {
return 0;
}
/*case 2: A+A+A+...A[N-2] = 0*/
if (begin [A.length-2] == 0) {
return A.length-1;
}
/*case 3: A+A+A[k-1] = A[k+1]+...+A[N-1] = 0*/
for (int k = 1; k < A.length - 1; k++) {
if(begin[k-1] == end[k+1])
return k;
}
return -1;
}
}
``````

It failed in the test, and after a careful review I find the mising points below:

input validation

``````if (A == null || A.length == 0 ) {
return -1;
}

if (A.length > 100000) {
return -1;
}

if (A.length == 1) {
return 0;
}
``````

wrong primitive type

Should use long for array `begin` and `end` to avoid arithmetic overflow.

What I get from this quize is that:
Although it's a quite easy task, before committing the code I need more reviews and tests.