Problem
write a code to find the equilibrium position of the array.
given an array: 3,-3,8,6,-1,-5
equilibrium position should be 2(element 8) sum of lower index(3+-3)=sum of higher index(6+(-1)+(-5))
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find the equilibrium position of the array
Created Date : 27-July-2013
Last Modified :
===========================================================================
*/
#include <iomanip>
#include <iostream>
#include <cassert>
#include <numeric>
using namespace std;
int FindEquilibriumPostion(int* arr, int len)
{
assert(arr != NULL);
assert(len > 2);
int leftSum(0);
int sum = accumulate(arr, arr + len, 0);
for(int i = 1; i < len - 1; ++i){
leftSum += arr[i - 1];
if( leftSum * 2 == sum - arr[i]) return i;
}
return -1;
}
void DoTest(int* arr, int len)
{
assert(arr != NULL);
assert(len > 2);
cout << "The array is " << endl;
for(int i = 0; i < len; ++i){
cout << setw(4) << arr[i];
}
cout << endl;
int pos = FindEquilibriumPostion(arr, len);
if(pos != -1){
cout << "The equilibrium position is " ;
cout << pos << endl;
}
else{
cout << "Cannot find an equilibrium position" << endl;
}
cout << " -------------------------" << endl;
}
int main(int argc, char* argv[])
{
for(int i = 0; i < 20; ++i){
cout << setw(4) << i;
}
cout << endl;
int arr[] = { 3,-3,8,6,-1,-5 };
DoTest(arr, sizeof(arr) /sizeof(arr[0]));
int arr1[] = { 3,-3,8};
DoTest(arr1, sizeof(arr1) /sizeof(arr1[0]));
int arr2[] = { 3,-3,8, 1, 2, 3, 4, 5, 6};
DoTest(arr2, sizeof(arr2) /sizeof(arr2[0]));
int arr3[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9};
DoTest(arr3, sizeof(arr3) /sizeof(arr3[0]));
int arr4[] = { 1, 2, 3, 4, 5, 6, 7, 8};
DoTest(arr4, sizeof(arr4) /sizeof(arr4[0]));
int arr5[] = { 0, 0, 0, 0, 0, 0, 0, 0};
DoTest(arr5, sizeof(arr5) /sizeof(arr5[0]));
int arr6[] = { 1, 1, 1, 1, 1, 1, 1, 1};
DoTest(arr6, sizeof(arr6) /sizeof(arr6[0]));
int arr7[] = { 1, 1, 1, 1, 1, 1, 1, 1, 1};
DoTest(arr7, sizeof(arr7) /sizeof(arr7[0]));
return 0;
}
Output
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
The array is
3 -3 8 6 -1 -5
The equilibrium position is 2
-------------------------
The array is
3 -3 8
Cannot find an equilibrium position
-------------------------
The array is
3 -3 8 1 2 3 4 5 6
Cannot find an equilibrium position
-------------------------
The array is
1 2 3 4 5 6 7 8 9
Cannot find an equilibrium position
-------------------------
The array is
1 2 3 4 5 6 7 8
The equilibrium position is 5
-------------------------
The array is
0 0 0 0 0 0 0 0
The equilibrium position is 1
-------------------------
The array is
1 1 1 1 1 1 1 1
Cannot find an equilibrium position
-------------------------
The array is
1 1 1 1 1 1 1 1 1
The equilibrium position is 4
-------------------------
Press any key to continue . . .