An equilibrium index of a sequence is an index into the sequence such that the sum of elements at lower indices is equal to the sum of elements at higher indices.



For example, in a sequence   



A


{\displaystyle A}

:

   




A

0


=
−
7


{\displaystyle A_{0}=-7}


   




A

1


=
1


{\displaystyle A_{1}=1}


   




A

2


=
5


{\displaystyle A_{2}=5}


   




A

3


=
2


{\displaystyle A_{3}=2}


   




A

4


=
−
4


{\displaystyle A_{4}=-4}


   




A

5


=
3


{\displaystyle A_{5}=3}


   




A

6


=
0


{\displaystyle A_{6}=0}


3   is an equilibrium index, because:

   




A

0


+

A

1


+

A

2


=

A

4


+

A

5


+

A

6




{\displaystyle A_{0}+A_{1}+A_{2}=A_{4}+A_{5}+A_{6}}


6   is also an equilibrium index, because:

   




A

0


+

A

1


+

A

2


+

A

3


+

A

4


+

A

5


=
0


{\displaystyle A_{0}+A_{1}+A_{2}+A_{3}+A_{4}+A_{5}=0}


(sum of zero elements is zero)

7   is not an equilibrium index, because it is not a valid index of sequence 



A


{\displaystyle A}

.



Task;
Write a function that, given a sequence, returns its equilibrium indices (if any).

Assume that the sequence may be very long.




#include <stdio.h>
#include <stdlib.h>
 
int list[] = {-7, 1, 5, 2, -4, 3, 0};
 
int eq_idx(int *a, int len, int **ret)
{
	int i, sum, s, cnt;
	/* alloc long enough: if we can afford the original list,
	 * we should be able to afford to this.  Beats a potential
         * million realloc() calls.  Even if memory is a real concern,
         * there's no garantee the result is shorter than the input anyway */
        cnt = s = sum = 0;
	*ret = malloc(sizeof(int) * len);
 
	for (i = 0; i < len; i++)
                sum += a[i];
 
	for (i = 0; i < len; i++) {
		if (s * 2 + a[i] == sum) {
			(*ret)[cnt] = i;
                        cnt++;
                }
		s += a[i];
	}
 
        /* uncouraged way to use realloc since it can leak memory, for example */
	*ret = realloc(*ret, cnt * sizeof(int));
 
	return cnt;
}
 
int main()
{
	int i, cnt, *idx;
	cnt = eq_idx(list, sizeof(list) / sizeof(int), &idx);
 
	printf("Found:");
	for (i = 0; i < cnt; i++)
                printf(" %d", idx[i]);
	printf("\n");
 
	return 0;
}