CareerCup

here first we traverse the array once to find total sum of array....

then we again start from 0th position and start subtracting value from total sum and go on adding it to leftsum and then compare leftsum and total remaining sum

#include<stdio.h>
 
int equil(int arr[],int size)
{
        int i=0,arrsum=0;
        int leftsum=0;
 
        for(i=0;i<size;i++)
                arrsum+=arr[i];
 
        for(i=0;i<size;i++)
        {
                arrsum-= arr[i];
                
                if(leftsum == arrsum)   
                        return i;
 
                leftsum+=arr[i];
        }
 
        return -1;
}
 
 
int main()
{
        int arr[] = {-7, 1, 5, 2, -4, 3, 0};
        int size = sizeof(arr)/sizeof(arr[0]);
        printf("Equilibrium index is : %d",equil(arr,size));
 
        return 0;
        
}

Hint: Start from both the ends..

void find_balance_index() {
	int a[]= {1,3,4,6,7,2,5,9,1,11,9,6,5,8,9,1}, i=0, j=0, sum_l=0, sum_r=0;

	j = ARRAY_SIZE(a) - 1;
//	if(j%2==0) { printf("-%d---No balance can be found----\n", j); exit(0); }
	while(i<j) {
			//printf("Indice Values: %d -- %d\n", a[i], a[j]);
			if(sum_l < sum_r)
				sum_l += a[i++];
			else sum_r += a[j--];;
			printf("Indices: %d -- %d\t\t", i, j);
			printf("SUMs: %d -- %d\n", sum_l, sum_r);
	
	}
	if(sum_l == sum_r) printf("Finally The balance is @ %d \n", i);
	else printf("-Final---No balance can be found----\n");
}

int retind(int size)
{
float f=sqrt((size*size-size)/2);
int i=f;
if((f-i)>0)
return -1
else
return i;
}

i think this will fix it up..........

edit :
sum of array - sum of array (1 to i-1 ) = ( sum of array - sum of array (i+1 to length of array ) then return i.

Is the array sorted?
If it is sorted than take one index i=0 and other index j=n-1;

int get_balance_index(int a[n])
{
sum_l=a[i]; sum_r=a[j];
while(1){
	if(i>=j )
	{
		if(sum_l==sum_r) 
			return i;
		else
			return -1;
	}
	if( i+1<j &&sum_l<sum_r)
		sum_l+=a[++i];
	else if(i< j-1 && sum_l>sum_r)
		sum_r+=a[--j];
}

If it is not sorted traverse 2 times

int get_index_point(int a[n])
{
int sum=0;
//calculate sum
for(int i=0;i<n-1;i++)
	sum+=a[i];

//calculate sum/2	
int sum_half=0;
for(int i=0; sum_half<sum/2; i++)
	sum_half+=a[i];
//Sum(a[0..i-1]) = Sum(a[i..n-1])	
if(sum_half-a[i]==sum/2) 
	return i-1;
else 
	return -1;
}

Here, for every i, you have to compute 2 subarray sums: [0, i-1] and [i+1, N-1]. This can be done by maintaining a sum[] array where sum[i] is the sum of the array from 0 to i (inclusive).

The solution of this problem can be achieved by Divide and Conquer rule.
Let us take above mentioned array = {10,4,3,2,5}

1. Find the middle index of the array,In this case index is (0 + 5)/2 = 2.
2. Calculate the sum of two subarrays (Left subarray starting from 0 to index - 1 and right subarray starting from index + 1 to end) and check the condition.In this case left subarray sum up to 10 + 4 = 14 and right subarray 2 + 5 =7.
3. That means now we need to shift the index from 2nd to left.Now the new index is (0 + 2)/2 = 1
4. Left subarray contains 10 and right subarray sum up to 3+ 2 + 5 = 10.So the index is 1 in this case.

int compute_index(int arr[],int size)
{
int sum1=0,sum2=0;
int i=0,j=size-1;
for( ;i<10 && j>=0;)
{
if(sum1==sum2 && i==j)
return i;
else if(i==j)
return -1;
else if(sum1>sum2)
sum2 =sum2+arr[j--];
else if(sum2>sum1)
sum1=sum1+ arr[i++];
else if(sum2==sum1)
{
sum1 =sum1+arr[i++];
sum2 =sum2+arr[j--];
}
cout<<i<<" "<<j<<" sum1: "<<sum1<<" sum2: "<<sum2<<endl;
}
}

public static int GetBalancedIndex(int[] inputArray)
        {


            Int64 arraySum = 0;
            Int64 leftSumt = 0;
            for (int i = 0; i < inputArray.Length; i++)
            {
                Console.Write(inputArray[i] + " , ");
                arraySum += inputArray[i];
            }
            Console.WriteLine();
            for (int i = 0; i < inputArray.Length; i++)
            {
                leftSumt += inputArray[i];
                arraySum -= inputArray[i];
                if (arraySum == leftSumt)
                {
                    Console.WriteLine("Balanced Index {0} : ", i);
                    return i;
                }

            }
            return -1;


        }

This is a simple question. Why are we making it complicated. "Student" has already given the solution.

#include<conio.h>
#include<stdio.h>

int balpoint(int a[],int size);
int main()
{
    int arr[]={1,3,4,6,7,2,5,9,1,11,9,6,5,8,9,1};
    int size= sizeof(arr)/sizeof(arr[0]);
    printf("balanced index=%d",balpoint(arr,size));
    getch();
    return 0;
}


int balpoint(int a[],int size)
{
    int leftsum=0;
    int rightsum=0;
    int i=0;
    leftsum=a[0];
    for(i=2;i<size;i++)
      rightsum +=a[i];
    if(leftsum==rightsum)
        return 1;
    else
    {
        for(i=2;i<size-1;i++)
        {
            leftsum +=a[i-1];
            rightsum -=a[i];
            if(leftsum==rightsum)
                return i;
                }
                }
   
   return -1;
}

//if the array is sorted
	//worst case complexity O(n)
	static void sortedArrayApproch(int sortedArray[]){
		if(null==sortedArray ){
			System.out.println("not threr");
			System.exit(0);
		}
		int i=0, j = sortedArray.length-1, leftsum=0, rightsum =0;
		int loopcount =0;
		System.out.println(sortedArray.length);
		while(i<j){
			loopcount++;
			if(leftsum<rightsum)
				leftsum+=sortedArray[i++];
			else
				rightsum+=sortedArray[j--];
			if(((j-i)*sortedArray[j])<Math.abs(rightsum-leftsum)){
				System.out.println(loopcount);
				System.out.println("cannot be fount");
				System.exit(0);
			}
		}
		System.out.println(loopcount);
		if(leftsum == rightsum)
			System.out.println(i);
		else
			System.out.println("not there");
	}
	//if we does not know whether array is sorted
	//O(n)
	static void  unSortedArrayApproch(int a[]){
		if(null==a ){
			System.out.println("not threr");
			System.exit(0);
		}
		int i=0, j = a.length-1, leftsum=0, rightsum =0;
		while(i<j){
			if(leftsum<rightsum)
				leftsum+=a[i++];
			else
				rightsum+=a[j--];
		}
		if(leftsum == rightsum)
			System.out.println(i);
		else
			System.out.println("not there");
	}

int index(int arr[],int size)
{
int leftsum=0, rytsum=0, i=0, j=size-1;
while(i!=j)
{
if(leftsum>rytsum)
{
rytsum+=arr[j];
j--;
}
else
{
leftsum+=arr[i];
i++;
}
if(leftsum==rytsum)
cout<<i;
else
count<<"not poss";

While @student already gave a correct answer, I think there's another simple approach to this problem, it does require O(n) space though (so I wouldn't argue this is better than @student's solution)

The idea is to create an auxiliary array which contains the accumulative sum of the original array, then scan through the auxiliary array for element that is exactly half of the last element

int FindEquilibriumSimple(const vector<float >& input) {
  int num_elem = input.size();
  vector<float> sums(num_elem, 0);
  sums[0] = input[0];
  for (int i = 1; i < num_elem; ++i) {
    sums[i] = sums[i-1] + input[i];
  }
  
  float target = sums[num_elem - 1] / 2;
  for (int i = 0; i < num_elem - 1; ++i) {
    if (sums[i] == target) // better to use abs diff < eps
      return i;
  }
  
  return -1;
}

I have implemented both approach and from the test cases I provided so far they produce the same result, try it out here: ideone.com/bsc0f

Here is a solution in C#

public int FindbalancedIndex(int[] array)        
        {            
            int low = 0;
            int high = array.Length-1;

            int lsum=array[low];//sum of array members starting from left
            int rsum=array[high];////sum of array members starting from right

            while (low < high-1)
            {                
                if (lsum == rsum) //add to both sums and increment both indices
                {
                    lsum += array[++low];
                    rsum += array[++high];

                }
                else if (lsum < rsum)                
                    lsum += array[++low];                
                else                
                    rsum += array[--high];
                
            }
            return (lsum == rsum) ? low : -1;
        }

public static int getIndex(int[] array)
    {
        
        if(array.length==1)
            return 0;
        
        int sum= getSum(array);
        
        int headSum= 0;
        int tailSum= sum - array[0];
        
        for(int i=1; i<array.length-1; i++)
        {
            headSum+= array[i-1];
            tailSum-= array[i];
            
            if(headSum==tailSum)
                return i;
        }
        
        return -1;
    }

public static void findBalancedIndex(int[] inpArr) {
		int i = 0;
		int j = inpArr.length-1;
		int leftSum = inpArr[i];
		int rightSum = inpArr[j];
		while(i!=j) {
			if(leftSum > rightSum) {
				j--;
				rightSum += inpArr[j];
			} else {
				i++;
				leftSum += inpArr[i];
			}
		}
		if(leftSum == rightSum) {
			System.out.println("Balanced index is " + (i+1));
		} else {
			System.out.println("Balanced index does not exist");
		}
	}

Question:
array: 1 1 0 0 0 1 1
we have three equilibrium point in this array. Which one should we return?

private static int returnBalanceIndex(int[] input) {


int sum = input[0];
for (int i = 1; i < input.length; i++) {
sum +=input[i];
}

int sumleft = input[0];

System.out.println(sum);

for (int i = 1; i < input.length; i++) {
if(sum - input[i]== (2* sumleft) ){
return i ;}
sumleft +=input[i];

}

return -1;
}

private static int returnBalanceIndex(int[] input) {
		

		int sum = input[0];
		for (int i = 1; i < input.length; i++) {
			sum +=input[i];
		}
		
		int sumleft = input[0];

		System.out.println(sum);
		
		for (int i = 1; i < input.length; i++) {
			if(sum - input[i]== (2* sumleft) ){
				return i ;}
			sumleft +=input[i];

		} 
		
		return -1;
	}