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

Question

I conducted a C ++ test with a request for a function that returns one of the indices that splits the input vector into 2 parts with the same sum of elements, for example: for vec = {1, 2, 3, 5, 4, -1, 1, 1, 2, -1} it can return 3, because 1 + 2 + 3 = 6 = 4-1 + 1 + 1 + 2-1. So I executed a 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 that the input was a very long vector containing only 1 (or -1), the return of the function was slow. Therefore, I thought about starting the search for the desired index from the middle, and then go left and right. But the best approach, I suppose, is where the index is in the order of the merge sort algorithm, which 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 should mention that I conducted the test a few days ago, so I forgot to indicate and not to mention part of the solution: it should return -1 ... I also updated the title of the question.

Answer 1

In particular, for this problem, I would use the following algorithm:

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

This gives the algorithm o (n) 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 elements p , and s2 will contain the sum of the rest. You can update them both with addition and subtraction when moving to the next element.

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

Answer 3

Given MSalters comments, I am afraid that another solution would be better. If you want to use less memory, the selected answer may be good enough, but you can use the following code to find possible solutions:

 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; 

Thus, you get all possible solutions. If there is no solution to split the vector into two equal halves, then mid_indices will remain empty. Again, you should sum each value only once.

My suggestion 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 adds each value only once no matter how many values. Such complexity is only O (n), not O (n ^ 2).

The code just runs left and right at the same time and moves the indexes further if it is smaller than the other. C>

Answer 4

To answer the real 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 ... 

those. the denominator works from i = 2 up in powers of 2, and the nominator works from j = 1 to i-1 with step 2. However, this is not what you need for your real problem, because the example you give has n = 10. It is clear that you do not want n / 4 there - your indices must be integer.

The best solution here is recursion. For the range [b, e], select the average value (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 a length of 1 or 2.

Answer 5

You want to use n ^{th the} term of the mentioned series. Then it will 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 answer above (some of the unit tests did not pass), but below the 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 Balance Point: 1

Answer 7

Here is the algorithm in Javascript:

 function equi(arr){ var N = arr.length; if (N == 0){ return -1}; var suma = 0; for (var i=0; i<N; i++){ suma += arr[i]; } var suma_iz = 0; for(i=0; i<N; i++){ var suma_de = suma - suma_iz - arr[i]; if (suma_iz == suma_de){ return i}; suma_iz += arr[i]; } return -1; 

}

As you can see, this code satisfies the condition O (n)