sop sop - 1 year ago 57
C++ Question

How to get the equilibrium index of an array in O(n)?

I have done a test in C++ asking for a function that returns one of the indices that splits the input vector in 2 parts having the same sum of the elements, for eg: for the

vec = {1, 2, 3, 5, 4, -1, 1, 1, 2, -1}
, it may return 3, because 1+2+3 = 6 = 4-1+1+1+2-1. So I have done the function that returns the correct answer:

int func(const std::vector< int >& vecIn)
for (std::size_t p = 0; p < vecin.size(); p++)
if (std::accumulator(vecIn.begin(), vecIn.begin() + p, 0) ==
std::accumulator(vecIn.begin() + p + 1, vecIn.end(), 0))
return p;
return -1;

My problem was when the input was a very long vector containing just 1 (or -1), the return of the function was slow. So I have thought of starting the search for the wanted index from middle, and then go left and right. But the best approach I suppose is the one where the index is in the merge-sort algorithm order, that means: n/2, n/4, 3n/4, n/8, 3n/8, 5n/8, 7n/8... where n is the size of the vector. Is there a way to write this order in a formula, so I can apply it in my function?


After some comments I have to mention that I had done the test a few days ago, so I have forgot to put and mention the part of no solution: it should return -1... I have updated also the question title.

Answer Source

Specifically for this problem, I would use the following algorithm:

  1. Compute the total sum of the vector. This gives two sums (empty vector, and full vector)
  2. for each element in order, move one element from full to empty, which means adding the value of next element from sum(full) to sum(empty). When the two sums are equal, you have found your index.

This give a o(n) algorithm instead of o(n2)

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download