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

Question

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?

Thanks

---

EDIT 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 1

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)

Answer 2

You can solve the problem much faster without calling std::accumulator at each step:

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

This is O(n). At each step, s1 will contain the sum of the first p elements, and s2 the sum of the rest. You can update both of them with an addition and a subtraction when moving to the next element.

Since std::accumulator needs to iterate over the range you give it, your algorithm was O(n^2), which is why it was so slow for many elements.

Answer 3

To answer the actual question: Your sequence n/2, n/4, 3n/5, n/8, 3n/8 can be rewritten as

1*n/2
1*n/4 3*n/4
1*n/8 3*n/8 5*n/8 7*n/8
...

that is to say, the denominator runs from i=2 up in powers of 2, and the nominator runs from j=1 to i-1 in steps of 2. However, this is not what you need for your actual problem, because the example you give has n=10. Clearly you don't want n/4 there - your indices have to be integer.

The best solution here is to recurse. Given a range [b,e], pick a value middle (b+e/2) and set the new ranges to [b, (b+e/2)-1] and [(b+e/2)=1, e]. Of course, specialize ranges with length 1 or 2.

Answer 4

Considering MSalters comments, I'm afraid another solution would be better. If you want to use less memory, maybe the selected answer is good enough, but to find the possibly multiple solutions you could use the following code:

static const int arr[] = {5,-10,10,-10,10,1,1,1,1,1};
std::vector<int> vec (arr, arr + sizeof(arr) / sizeof(arr[0]) );

// compute cumulative sum
std::vector<int> cumulative_sum( vec.size() );
cumulative_sum[0] = vec[0];
for ( size_t i = 1; i < vec.size(); i++ )
{ cumulative_sum[i] = cumulative_sum[i-1] + vec[i]; }

const int complete_sum = cumulative_sum.back();

// find multiple solutions, if there are any
const int complete_sum_half = complete_sum / 2; // suggesting this is valid...
std::vector<int>::iterator it = cumulative_sum.begin();
std::vector<int> mid_indices;
do {
  it = std::find( it, cumulative_sum.end(), complete_sum_half );

  if ( it != cumulative_sum.end() )
  { mid_indices.push_back( it - cumulative_sum.begin() ); ++it; }

} while( it != cumulative_sum.end() );

for ( size_t i = 0; i < mid_indices.size(); i++ )
{ std::cout << mid_indices[i] << std::endl; }

std::cout << "Split behind these indices to obtain two equal halfs." << std::endl;

This way, you get all the possible solutions. If there is no solution to split the vector in two equal halfs, mid_indices will be left empty. Again, you have to sum up each value only once.

My proposal is this:

static const int arr[] = {1,2,3,5,4,-1,1,1,2,-1};
std::vector<int> vec (arr, arr + sizeof(arr) / sizeof(arr[0]) );

int idx1(0), idx2(vec.size()-1);
int sum1(0), sum2(0);
int idxMid = -1;
do {
  // fast access without using the index each time.
  const int& val1 = vec[idx1];
  const int& val2 = vec[idx2];

  // Precompute the next (possible) sum values. 
  const int nSum1 = sum1 + val1;
  const int nSum2 = sum2 + val2;

  // move the index considering the balanace between the 
  // left and right sum.
  if ( sum1 - nSum2 < sum2 - nSum1 )
  { sum1 = nSum1; idx1++; }
  else
  { sum2 = nSum2; idx2--; }

  if ( idx1 >= idx2 ){ idxMid = idx2; }

} while( idxMid < 0 && idx2 >= 0 && idx1 < vec.size() );

std::cout << idxMid << std::endl;

It does add every value only once no matter how many values. Such that it's complexity is only O(n) and not O(n^2).

The code simply runs from left and right simultanuously and moves the indices further if it's side is lower than the other.

Answer 5

You want n^th term of the series you mentioned. Then it would be:

numerator:   (n - 2^((int)(log2 n)) ) *2 + 1
denominator:  2^((int)(log2 n) + 1) 

Answer 6

I came across the same question in Codility tests. There is a similar looking answer above (didn't pass some of the unit tests), but below code segment was successful in tests.

#include <vector>
#include <numeric>
#include <iostream>

using namespace std;

// Returns -1 if equilibrium point is not found
// use long long to support bigger ranges
int FindEquilibriumPoint(vector<long> &values) {
    long long lower = 0;
    long long upper = std::accumulate(values.begin(), values.end(), 0);

    for (std::size_t i = 0; i < values.size(); i++) {

        upper -= values[i];

        if (lower == upper) {
            return i;
        }

        lower += values[i];
    }

    return -1;
}


int main() {
        vector<long> v = {-1, 3, -4, 5, 1, -6, 2, 1};

        cout << "Equilibrium Point:" << FindEquilibriumPoint(v) << endl;

        return 0;
}

Output Equilibrium Point:1