CareerCup

Here is the main idea :

1. Caluculate the whole sum of elements presented in the Array
2. Maintain a variable which holds the sum of elements till that elements i.e.CumSum ( excludes present element).

3. Return the index of the array when 2*CumSum+ current element = sum of all elements in the array

for(int i =0; i< N; ++i)
{
sum += x[i];
}

int sum_right = sum - x[0] - x[1];
int sum_left = x[0];
int index = 1;
if(sum_right == sum_left)
{
return index;
}

for(int j = 2; j < N; ++j)
{
sum_left += x[j-1];
sum_right -= x[j];
if(sum_right == sum_left)
{
cout<<"Index is :"<<j<<endl;
break;
}
}

cout<<"Index is :"<<"-1"<<endl;

Small Correction:

sum_left += x[j-1];
sum_right -= x[j];

public static int getEqualIndex(int[] array)
	{
		if (array.length <= 2)
		{
			return -1;
		}
	
		int posLeft = 0;
		int posRight = array.length - 1;
		int sumLeft = array[posLeft];
		int sumRight = array[posRight];
		
		while (posLeft + 2 != posRight)
		{
			if (sumLeft <= sumRight)
			{
				sumLeft += array[++posLeft];
			}
			else
			{
				sumRight += array[--posRight];
			}
		}
			
		return (sumLeft == sumRight)? posLeft + 1: -1;
	}

public class DivideArrayinEqual {

public static void main(String st[])
{
int a[]={-1, -2, 0, -3};
int sum = 0;
for(int i =0 ;i<a.length;i++)
{
sum = a[i]+sum;
}
int sumleft =0;
// sum = sum-a[0];
for(int i=0;i<a.length;i++)
{
sumleft =sumleft+a[i];
if(sumleft == sum-sumleft)
{
System.out.println("sum equal at i ="+i);
return;
}
}
}
}

int DivideArray(int *a,int length)
{
	int l=0;
	int r=length-1;
	if(length<2) return -1;
	int leftSum = a[l];
	int rightSum =a[r];
	while (l<r)
        {
		if(l==r-1)
                {
			if(leftSum ==rightSum ) 
				return 1;//true
			return -1;//false
		}
		if(abs(leftSum ) < abs(rightSum)) //abs=absolute value
		{
			l++;
			leftSum += a[l];
		}
		else
		{
			r--;
			rightSum += a[r];
		}
	}
	return -1
}

let A be the array.
Take two more array B and C of same size as A

store the running sum of elements of A from left to right in array B
b[0] = 0;
for(int i = 1 ; i < n ; i++)
b[i] = b[i-1] + a[i-1];

store the running sum of elements of A from right to left in array C
C[n-1] = 0;
for(int i = n-2 ; i >= 0 ; i--)
C[i] = c[i+1] + a[i+1];

return the index for which B[i] == C[i]]

array : 1 2 3 4 5 4 3 2 1
cumulative_sum : 1 3 6 10 15 19 22 24 25

Find i from cumulative_sum array so that
cumulative_sum [i-1] = cumulative_sum[lastElement] - cumulative_sum[i]

Time complexity n (for finding cumu sum) + n (for finding i) = O(n)

o(n) sol:tested n worked in all possitive n negative numbers:

public static void eqiSumIndex(int[] a)
{
int sm = 0;
int t = 0;
for (int i = 0; i < a.Length; i++)
{
sm += a[i];
}
for (int i = 1; i <= a.Length; i++)
{
t += a[i-1];
if ((i >= 1)&&(i<a.Length))
{
if (((sm-a[i]) / 2) == t)
{
Console.WriteLine("The posn:" + (i+1));
break;
}
}
if (i == a.Length)
{
Console.WriteLine("Posn:Not Found");
}

}

}

o(n) sol:tested n worked in all positive n negative numbers:

public static void eqiSumIndex(int[] a)
{
int sm = 0;
int t = 0;
for (int i = 0; i < a.Length; i++)
{
sm += a[i];
}
for (int i = 1; i <= a.Length; i++)
{
t += a[i-1];
if ((i >= 1)&&(i<a.Length))
{
if (((sm-a[i]) / 2) == t)
{
Console.WriteLine("The posn:" + (i+1));
break;
}
}
if (i == a.Length)
{
Console.WriteLine("Posn:Not Found");
}

}

}

int dividearray(int *arr, int size)
{
	if (size == 1)
		return -1;
	int *begin = arr, *end = arr + size -1;
	int bsum = *begin, esum = *end;

	for(int i = 0; i < size; i++)
	{
		if (begin == end-1) {
			if (bsum == esum)
				printf("%x %x idx=%d\n", begin, end-1, begin - arr);
			else
				printf("cannot be divided\n");
			return begin - arr;
		}
		if (bsum <= esum)
			bsum += *(++begin);
		else 
			esum += *(--end);
	}

}

This should do it:

int left = 0;
        int right = arr.length - 1;

        int leftSum = arr[left];
        int rightSum = arr[right];

        while (left < right - 1) {
            if (Math.abs(leftSum) > Math.abs(rightSum)) {
                right--;
                rightSum += arr[right];
            } else if (Math.abs(rightSum) > Math.abs(leftSum)) {
                left++
                leftSum += arr[left];
            } else {
                left++;
                right--;
                leftSum += arr[left];
                rightSum += arr[right];
            }
        }

Let me clean it up a bit more:

Idea: We iterate from both ends, 'till the indices are the same (or we've crossed over).

If the sum of the numbers we have so far encountered on the left is less than the sum of the numbers we have encountered on the right, the we increment the left index.

If the sum of the numbers we have so far encountered on the left is greater than the sum of the numbers we have encountered on the right, the we decrement the right index.

Otherwise, the sums are the same, so we increment the left index, and decrement the right index.

Keep repeating till both indices are the same. This runs in O(n) time.

function (arr) {

    var left = 0;
    var right = arr.length - 1;

    var leftSum = arr[left];
    var rightSum = arr[right];

    while (left < right - 1) {
        if (Math.abs(leftSum) > Math.abs(rightSum)) {
            right--;
            rightSum += arr[right];
        } else if (Math.abs(rightSum) > Math.abs(leftSum)) {
            left++
            leftSum += arr[left];
        } else {
            left++;
            right--;
            leftSum += arr[left];
            rightSum += arr[right];
        }
    }

    // Cannot divide the array into two equal sum parts
    if (leftSum != rightSum) {
        return -1;
    }

    // return the index
    return left;
}

let the total sum be s. if s is even, check if the cumulative sum upto index i = s/2. if yes return index.... if s is odd then return false..

<pre lang="" line="1" title="CodeMonkey89549" class="run-this">// Working solution, O(n), only constant extra space used
class HalfArraySum {

public static void main(String[] args) {
// A few test cases
int[] nums = { 1, 5, 3, 4, -1, 3, 5, -2, 9, 6, 2 };
System.out.println(findIndex(nums));

int[] nums2 = { -1, -2, 0, -3 };
System.out.println(findIndex(nums2));

int[] nums3 = { 1 };
System.out.println(findIndex(nums3));

int[] nums4 = {};
System.out.println(findIndex(nums4));
}

private static int findIndex(int[] nums) {
// Keep a total of the array
long total = 0;
for (int n : nums) {
total += n;
}

// Start with the left side having 0
long left = 0;

// And the right side having everything
long right = total;

// Look at the first index, remove that number from the right side.
// If the current left side total == right side return
// else, add that index's value to the left total and remove the next
// index value from the right total
for (int i = 0; i < nums.length; i++) {
right = right - nums[i];
if (right == left) {
return i;
}
left = left + nums[i];
}

// If we got here there's no possible solution
return -1;
}
}
</pre>

traverse the array online one time.

int i=1, j=length-2;
int Lsum=array[0], Rsum=array[length-1]
while(i<j-1){
	while(Lsum<Rsum && i<j-1){
		i++;
		Lsum += array[i]
	}
	while(Lsum>Rsum && i<j-1){
		j--
		Rsum += array[j]
	}
	if(Lsum == Rsum && i= j-2)
		return i+1;
}
return -1