CareerCup

1. Find the total sum of the array
2. For each element in the array
2.a. keep contSum, which is the sum up to the point in the array
2.b. if the (sum - A[i] - contSum) == contSum, return index (This is the point where the leftSum and the rightSum equals)
3. Return -1 if not found

public static int equilibriumIndex(int[] A) {
	int sum = 0;
	int i = 0;
	for (i = 0; i < A.length; i++) 
		sum += A[i];
		
	int contSum = 0;
	for (i = 0; i < A.length; i++) {
		if ( (sum - A[i] - contSum) == contSum) return i;
			
		contSum += A[i];
	}
		
	return -1; // not found
}

def equilibrium(list):
    leftsum = rightsum = 0
    left = []
    for i in range(0, len(list)):
        leftsum += list[i]
        left.append(leftsum)
    for i in range(0, len(list)):
        rightsum += list[-(i+1)]
        if left[len(list) - i - 1] == rightsum:
            return list[-(i + 1)]

#include<iostream>
using namespace std;
int equilibrium(int * arr, int size){
        int sum = 0;
        int left_sum = 0;
        for (int i = 0; i<size; i++){
                sum+=arr[i];
        }
        for(int i = 0; i<size; i++){
                sum -= arr[i];
                if(sum == left_sum) return i;
                else left_sum+=arr[i];
        }
        return -1;
}
int main(){
        int arr[] = {3,-3,8,6,-1,-5};
        int size = 6;
        int equil = equilibrium(arr, size);
        cout<<equil;
}

arr[] = 2 -3 4 -2 3 1

sumarray[i] = sum of all elements from index 0 to i

from start index sum_array_start[] = 2 -1 3 1 4 5
from end index sum_array_end[] = 5 3 6 2 4 1

now compare all elements in both sum arrays... at one index location the data is same in both sum_arrays, that index location is the equilibrium point index a[index]...
here 4 is same for both sum arrays and it is at index 4... so a[4] i.e 3 is equilibrium point

I suppose the following idea also should work.

0.Assuming 1-based index, for n elements, take mid = (n+1)/2.
1.Compute the sum from 1 to mid-1 and call it LSum
2.Compute the sum from mid +1 to n and call it RSum 
3. If LSum = RSum return mid
4. if LSum < RSum
   4a. whlle (LSum < RSum) {
        if (mid ==n) return -1;
	LSum += a[mid]
	RSum -= a[mid+1]
        mid = mid+1;
        if (LSum == RSum) 
		return mid;
        else if if (LSum > RSum)
            return -1; 
    }
5. if LSum > RSum
   4a. whlle (LSum > RSum) {
        if (mid == 1) return -1;
	LSum -= a[mid-1]
	RSum += a[mid]
        mid = mid-1;
        if (LSum == RSum) 
		return mid;
        else if (LSum < RSum)
            return -1; 
    }

C++ implementation time complexity o(n) and space o(1)

#include<iostream>
#include<stdio.h>
#include<stdlib.h>

int findPoint(int arr[],int size)  {
    int leftSum=arr[0];
    int rightSum=arr[size-1];
    int leftIndex=0;
    int rightIndex=size-1;
    while(true )    {
        if(leftSum>rightSum)    {
            rightSum=rightSum+arr[--rightIndex];
            if(leftSum==rightSum)   {
                return rightIndex-1;
            }
        }
        else    {
            leftSum=leftSum+arr[++leftIndex];
            if(leftSum==rightSum)   {
                return leftIndex+1;
            }
        }
    }
    return leftIndex;
}

int main()  {
    int arr[]={1,3,2,5,4,6,7,8};
    int point=findPoint(arr,sizeof(arr)/sizeof(arr[0]));
    std::cout<<point;
    return 0;
    
}

This is the simple methodical approach, loop through array to get the total sum. iterate back through the array from 1 to length - 1. subtracting each the value at each previous index , doing the comparison, and returning early when we find an equilibrium.

public class equilibriumApp
{
	
	public static void main(String args[])
	{
	
		int[] eqArray = { 1,2,3,4,3,2,1 };

		int equilibrium = findEquilibriumIndex(eqArray);
		System.out.println(equilibrium);

	}

	private static int findEquilibriumIndex(int[] eqArray)
	{
		int leftSum = 0,rightSum = 0;

		for(int i = 0; i < eqArray.length; i++)
		{
			rightSum += eqArray[i];
		}

		for(int j = 1; j < eqArray.length; j++)
		{
			leftSum += eqArray[j-1];
			rightSum-= eqArray[j-1];
			rightSum-= eqArray[j];

			if(leftSum == rightSum)
				return j;
			rightSum+= eqArray[j];				
		}

		return -1; //no equilibrium

	}
}

The way I solved is:

1. Calculate the sum of elements upto index i from left and store in ltemp[i] for all elements
2. Calculate the sum of elements upto index 0 from right and store in rtemp[i] for all elements
3. Find the index i where ltemp[i] is same as rtemp[i].

Time Complexity: O(n).
Space Complexity O(n) which can be optimized further if needed.

int main() {
    const int length = 6;
    int arr[length] = {3,-3,8,6,-1,-5};
    int rtemp[length];
    int ltemp[length];

    // Find the sum of elements from left to right
    int lsum = 0;
    for (int i = 0; i < length; i++) {
        lsum = lsum + arr[i];
        ltemp[i] = lsum;
    }
    // Here ltemp array will have values 3, 0, 8, 14, 13, 8

    // Find the sum of elements from right to left
    int rsum = 0;
    for (int i = length - 1; i >= 0; i--) {
        rsum = rsum + arr[i];
        rtemp[i] = rsum;
    }
    // Here rtemp array will have values 2, 5, 8, 0, -6, -5

    // Find the index i where rtemp[i] is same as ltemp[i]
    for (int i = 0; i < length; i++) {
        if (ltemp[i] == rtemp[i]) {
            cout << "Value = " << arr[i] << " and index = " << i << endl;
            return 0;
        }
    }

    return -1;
}

#include <stdio.h>

#define SIZE 15

int main(void)
{
int num[SIZE], i, sum = 0, count = 0, n, *p = num;

printf("Enter number of elements: ");
scanf("%d", &n);

for (i = 0; i < n; i++)
{
scanf("%d", &num[i]);
sum += num[i];
}

if (n % 2 == 0)
{
printf("\nEquilibrium number: 0");
return 0;
}

for (i = 0; i < SIZE; i++)
{
if ((sum - num[i] + count) == count)
{
printf("Equilibrium number: %d\n", num[i]);
break;
}
else
count += num[i];
}

return 0;
}

int findequilibrium()
{
int a[5]={-3, 2, 4, -2 ,3};//{-3,4,5,-8,10,-1};
int sum[5]={0};
sum[0]=a[0];
for(int i=0;i<4;i++)
{
sum[i+1]=sum[i]+a[i+1];
}
for(int j=0;j<5;j++)
{
if(sum[4]-sum[j+1]==sum[j])
return j+1;

}
return -1;
}

We can solve it using a modified "two-finger walking" method.

The idea is, we maintain a prefix sum and a suffix sum, with indexes lo and hi, respectively.

If prefix sum < suffix sum, we need to add one more element to prefix sum to try to make them equal.

Similarly, if prefix sum > suffix sum, we need to add one more element to suffix sum to try to make them equal.

Do this until there is only one element left in the array (lo = hi - 1), if the two sums are equal, then we found an equilibrium point (A[lo]); otherwise there is no equilibrium point.

Time: O(n)
Space: O(1)



public int equilibriumIndex(int[] A) {
/* Assume that the length of the array is always an odd number */
int prefixSum = A[0];
int suffixSum = A[A>length - 1];
int lo = 1;
int hi = A.length - 2;
while(lo < hi - 1) {
if (prefixSum < suffixSum) {
prefixSum += A[lo];
lo++;
}
else if (prefixSum > suffixSum) {
suffixSum += A[hi];
hi--;
}
else {
prefixSum += A[lo];
suffixSum += A[hi];
lo++;
hi++;
}
}
if (prefixSum != suffixSum)
no such equilibrium point
else
return A[lo];
}

@vgeek I had the same idea, but we need to traverse the array again to make sure the element which we get as sum is actually present in the array , if not present we need to say no equilibrium element present in the array

int main()
{
    int a[10]={2,2,-4,5,-6,6,10,-10};
    int x,y;
    for(int i=0;i<8;i++)
    {
        if(i==0)
            x=a[i]+a[i+1];
        else
        {
            y=x+a[i+1];
            x=y;
        }
    }
    int k=1;
    for(int j=0;j<8;j++)
    {
        if(a[j]==x)
        {
            k=0;
        }
    }
    if(k==0)
        std::cout<<"\n Equilibrium is:"<<x;
    else
        std::cout<<"\nNo equilibrium number found:";
    return 0;
}

//what about below code
int equilibriumIndex(int[] A)
{
int sumLeft=0;
int sumRight=0;
for(int i=0;i<length;i++)//length is length of array
{
sumLeft=sumLeft+a[i];
sumRight=sumRight+a[(length-1)-i];
if(sumLeft==sumRight && (length-1-i)==2)
return i+1;
}
return -1;
}

I think it can be done in a straight way:
a. Just sum all the elements in the array
b. The number that you will get after the sun that will be the equilbrium number as all others would have cancelled each other.
c. Find the index of that number in the array.