This is a demo task.
An array A consisting of N integers is given. An equilibrium index of this array is any integer P such that 0 ≤ P < N and the sum of elements of lower indices is equal to the sum of elements of higher indices, i.e.
A[0] + A[1] + ... + A[P−1] = A[P+1] + ... + A[N−2] + A[N−1].
Sum of zero elements is assumed to be equal to 0. This can happen if P = 0 or if P = N−1.
For example, consider the following array A consisting of N = 8 elements:
A[0] = -1 A[1] = 3 A[2] = -4 A[3] = 5 A[4] = 1 A[5] = -6 A[6] = 2 A[7] = 1P = 1 is an equilibrium index of this array, because:
- A[0] = −1 = A[2] + A[3] + A[4] + A[5] + A[6] + A[7]
P = 3 is an equilibrium index of this array, because:
- A[0] + A[1] + A[2] = −2 = A[4] + A[5] + A[6] + A[7]
P = 7 is also an equilibrium index, because:
- A[0] + A[1] + A[2] + A[3] + A[4] + A[5] + A[6] = 0
and there are no elements with indices greater than 7.
P = 8 is not an equilibrium index, because it does not fulfill the condition 0 ≤ P < N.
Write a function:
int solution(int A[], int N);
that, given an array A consisting of N integers, returns any of its equilibrium indices. The function should return −1 if no equilibrium index exists.
For example, given array A shown above, the function may return 1, 3 or 7, as explained above.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [0..100,000];
- each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
size_t i, sum1 = 0, sum2 = 0;
for (i = 0; i < N - 1; i++)
sum1 += A[i];
for (i = 1; i < N; i++)
sum2 += A[i];
for (i = 0; i < N; i++)
if (A[i] == sum1 || A[i] == sum2)
return i;
return -1;
}
Test from the task description
got 6, but it is not equilibrium point, sum[0..5]=-2, sum[7..7]=1
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
size_t i, sum1 = 0, sum2 = 0;
for (i = 0; i < N - 1; i++)
sum1 += A[i];
for (i = 1; i < N; i++)
sum2 += A[i];
for (i = 0; i < N; i++)
if (A[i] == sum1 || A[i] == sum2)
return i;
return -1;
}
Test from the task description
got 6, but it is not equilibrium point, sum[0..5]=-2, sum[7..7]=1
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int i, j;
for (j = 0; j < N; j++)
{
size_t sum1 = 0, sum2 = 0;
for (i = 0; i < j - 1; i++)
sum1 += A[i];
for (i = j; i < N; i++)
sum2 += A[i];
if (sum1 == sum2)
return j;
}
return -1;
}
Test from the task description
got 2, but it is not equilibrium point, sum[0..1]=2, sum[3..7]=3
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int i, j;
for (j = 0; j < N; j++)
{
size_t sum1 = 0, sum2 = 0;
for (i = 0; i < j - 1; i++)
sum1 += A[i];
for (i = j + 1; i < N; i++)
sum2 += A[i];
if (sum1 == sum2)
return j;
}
return -1;
}
Test from the task description
got 5, but it is not equilibrium point, sum[0..4]=4, sum[6..7]=3
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int i, j;
for (j = 0; j < N; j++)
{
size_t sum1 = 0, sum2 = 0;
for (i = 0; i < j - 1; i++)
sum1 += A[i];
for (i = j; i < N; i++)
sum2 += A[i];
if (sum1 == sum2)
return j;
}
return -1;
}
Test from the task description
got 2, but it is not equilibrium point, sum[0..1]=2, sum[3..7]=3
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N) {
// write your code in C99 (gcc 6.2.0)
int i, j;
for (j = 0; j < N; j++)
{
size_t sum1 = 0, sum2 = 0;
for (i = 0; i < j - 1; i++)
sum1 += A[i];
for (i = j; i < N; i++)
sum2 += A[i];
if (sum1 == sum2)
return j + 1;
}
return -1;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N) {
int i, j;
for (j = 0; j < N; j++)
{
int sum1 = 0, sum2 = 0;
for (i = 0; i < j - 1; i++)
sum1 += A[i];
for (i = j; i < N; i++)
sum2 += A[i];
if (sum1 == sum2)
return j + 1;
}
return -1;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N)
{
int i, j;
for (j = 0; j < N; j++)
{
int sum1 = 0, sum2 = 0;
for (i = 0; i < j - 1; i++)
sum1 += A[i];
for (i = j; i < N; i++)
sum2 += A[i];
if (sum1 == sum2)
return j + 1;
}
return -1;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int **A, int N)
{
int i, j;
for (j = 0; j < N; j++)
{
int sum1 = 0, sum2 = 0;
for (i = 0; i < j - 1; i++)
sum1 += A[i];
for (i = j; i < N; i++)
sum2 += A[i];
if (sum1 == sum2)
return j + 1;
}
return -1;
}
Test from the task description
got -1, but equilibrium point exists, for example on position 1
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N)
{
int i, j;
for (j = 0; j < N; j++)
{
int sum1 = 0, sum2 = 0;
for (i = 0; i < j - 1; i++)
sum1 += A[i];
for (i = j; i < N; i++)
sum2 += A[i];
if (sum1 == sum2)
return j + 1;
}
return -1;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N)
{
int i, j;
for (j = 0; j < N; j++)
{
size_t sum1 = 0, sum2 = 0;
for (i = 0; i < j - 1; i++)
sum1 += A[i];
for (i = j; i < N; i++)
sum2 += A[i];
if (sum1 == sum2)
return j + 1;
}
return -1;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N)
{
int i, j;
for (j = 0; j < N; j++)
{
size_t sum1 = 0, sum2 = 0;
for (i = 0; i < j - 1; i++)
sum1 += A[i];
for (i = j; i < N; i++)
sum2 += A[i];
if (sum1 == sum2)
return j + 1;
}
return -1;
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N)
{
int i, j;
for (j = 0; j < N; j++)
{
size_t sum1 = 0, sum2 = 0;
for (i = 0; i < j - 1; i++)
sum1 += A[i];
for (i = j; i < N; i++)
sum2 += A[i];
if (sum1 == sum2)
return j + 1;
}
return -1;
}
The following issues have been detected: wrong answers, timeout errors.
For example, for the input [0] the solution returned a wrong answer (got 1, which is not valid array index).
Sequence with extremely large numbers testing arithmetic overflow.
got 3, which is not valid array index
Sequence with extremely large numbers testing arithmetic overflow.
got -1, but equilibrium point exists, for example on position 0 of A = [-2147483648]
one large number at the end of the sequence
got 2, but it is not equilibrium point, sum[0..1]=501, sum[3..4]=1
sequence with sum=0
got 1, but it is not equilibrium point, sum[0..0]=1, sum[2..2]=-3
multiple runs, all pairs of values: -1, 0 and 1
got 2, which is not valid array index
multiple runs, all triples of values -1, 0 and 1
got 3, which is not valid array index
got 44, but it is not equilibrium point, sum[0..43]=-101, sum[45..444]=199
got 64, but it is not equilibrium point, sum[0..63]=-226, sum[65..964]=449
Large performance test, O(n^2) solutions should fail.
got 200, but it is not equilibrium point, sum[0..199]=-2402, sum[201..9804]=4801
Large performance test, O(n^2) solutions should fail.
got 632, but it is not equilibrium point, sum[0..631]=-24650, sum[633..99228]=49297