CareerCup

There is a very simple n^2 solution:

Loop through the 'gaps' in the array, where is n-1 gaps ( 2 gap 2 gap 13 gap 4...)

Check the two side of the gap. If they are equal, you have the first match.

If not, check whether the left or the right summary is larger and try to expand the array that way, and add the new element to the summary. If you hit a wall (beginning or end of array), stop and check the next gap.

The outer loop runs n-1, while the inner at most n steps (usually hitting wall), so it's a light n^2 solution.

Writing the code is really easy too (can share if you want to).

O(n^2) is possible. (Talking in terms of expected time, using hashtables).

Suppose there was a sub-array with the property. The sub-array will have a line of balance (or LOB) where the sum of elements to its left will equal the sum of elements to its right.

The algorithm, considers each possible LOB and tries to see if there is a sub-array which has that LOB.

For each LOB candidate, you maintain two hash tables, Land R.

L will contain the cumulative sum of elements, as you move from the LOB to the left end of the array. R will contain the cumulative sum of elements, as you move from LOB to the right end of the array.

To see if there is a sub-array with that LOB, all you need to do is check if L and R have any common value.

This can be done in O(n) (expected, because of hashtables) time, for each LOB.

Thus total time is O(n^2).

If you use a tree instead of hashtable, then it is worst case O(n^2 log n), still better than cubic.

Total space is O(n), as you can reuse L and R.

Here is the code..For explanation see my comment above...
The method return Pair object i.e. {start-index,end-index}

static class Pair{
		int start;
		int end;

		public Pair(int a,int b){
			start = a;
			end = b;
		}
		public boolean isGreaterthan(Pair p) {
			
			int size = end-start;
			if(size > (p.end - p.start))
				return true;
			return false;
			
		}
		public static Pair max(Pair p1, Pair p2, Pair p3) {
			Pair max = null;
			if(p1.end - p1.start > p2.end - p2.start)
				max = p1;
			else
				max = p2;
			
			if(p3.end - p3.start > max.end - max.start)
				max = p3;
			
			return max;
		}
	}

	static Pair findSubArray(int[] a, int start, int end){
		if(start>=end)
			return new Pair(-1,-1);
		//Calculate Sum Array
		for(int i = start+1;i<=end;i++){
			a[i] = a[i] + a[i-1];
		}
		
		int startindex = -1;
		int endindex = -1;
		HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
		
		for(int j = start;j<end;j++){
			map.put(2*a[j], j);
			if(map.containsKey(a[j])){
				int s = map.get(a[j]);
				if( (j - start) > (endindex - startindex)){
					endindex = j;
					startindex = start;
				}
			}	
		}
		
		Pair p1 = new Pair(startindex,endindex);
		
		//reset
		for(int i = end;i>start;i--){
			a[i] = a[i] - a[i-1];
		}
		
		Pair p2 = new Pair(-1,-1);
		Pair p3 = new Pair(-1,-1);
		if(end==a.length-1)
			p2 = findSubArray(a,start+1,end);
		if(start==0)
			p3 = findSubArray(a,start,end-1);
		return Pair.max(p1,p2,p3);
		
	}

Further clarification: k is not a given entity. It could be of any length. We need to return one such subarray of maximum length.

I think maximum sub array for the given example array is 2,13,4,7,3,8,12,9 because
2+13+4+7+3 = 29
8+12+9 = 29

I found an o(n^2) solution for this problem. Please find the below code for the problem.

We keep two sums sum1 and sum2 and another variable for finding the position of the element starting for sum2. We always keep the sum1 value greater than sum2. This is a simple logic. The following code prints the all possible arrays here we can track the maximum sub array using variables easily.

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

int main()
{
    int i, j, k, l, sum1, sum2;
    int a[11] = {2,2,13,4,7,3,8,12,9,1,5};
    for (i = 0; i < 11; i++) {
        sum1 = a[i];
        sum2 = 0;
        k = i+1;
        for(j = i+1; j < 11; j++) {
              sum2 += a[j];
              while (sum1 < sum2) {
                    sum2 -= a[k];
                    sum1 += a[k];
                    k += 1;
              }
              if (sum1 == sum2) {
                 printf("\nArray: ");
                 for (l= i; l < j+1; l++) {
                     printf("%d, ", a[l]);
                 }
              }
        }
    }
    getch();
    return 0;
}

for all positive number array arr[n]
say sum = sum of all n number in array.
get sum2 = sum of 0 to k elements
and sum1 = sum of k+1 -> n element, such that sum 2 >= sum
//if equal you got the answer.
t = 0;
for t = 0 to n
{
sum2 -= k[t];
//now sum2 will be less than sum1
move k right, such that sum2 >= sum1
//if sum2 == sum1, you got the result
}
over all complexity O(n)
However, if the array contains positive and negative, then this method will not work

Lets break the problem
1) If the array has an index j such that sum(0 to j) = sum(k-j to k) , we can identify this in O(n) ->
a) Calculate sum array i.e. for { 4,7,3,8,12,9,1} Sum Array will be {4,11,14,22,34,43,44}
b) Now go through loop once again and build hasmap of 2*thatelement, if we already have 2*that element in hash map, means we have found such an array store the start-index and end-index.
2) Now we have to find sub arrays , we can do that in O(n) too
a) first start full array i.e. 0 to length-1 then 1 to length -1 -> 2 - length-1 ... n times
b) start dropping element from end i.e. 0 to length -1 -> o - length -2 ... n times

Now step 2 is O(n) and at every step we will perform step 1 which is also 0(n), so the overall complexity is O(n^2)

Will post the code soon

int Sum(int[] a, int l, int j)
{
	int sum = 0;
	while (l < j)
		sum += a[l++];
	return sum;
}

int[] FindSubArray(int[] a)
{
	int range = a.Length;
	while (range-- > 0)
	{
		for (int lower = 0, upper = lower + range; upper < a.Length; ++lower, ++upper)
		{
			for (int mid = lower; mid < upper; ++mid)
			{
				if (Sum(a, lower, mid) == Sum(a, mid, upper))
				{
					int[] ret = new int[upper - lower];
					for (int i = 0; i < ret.Length; ++i)
						ret[i] = a[lower + i];
					return ret;
				}
			}
		}
	}
	return null;
}

private int getIndex(int[] arr, int start, int end)
        {
            if (start >= end)
                return -1;
            int[] forwardSum = new int[end + 1 - start];
            forwardSum[0] = 0;
            int j = 1;
            for (int i = start + 1; i <= end; i++)
            {
                forwardSum[j] = forwardSum[j - 1] + arr[i -1];
                j++;
            }

            j = 1;
            int jEnd = forwardSum.Length - 1;
            for (int i = start + 1; i <= end; i++)
            {
                if (forwardSum[j] == (forwardSum[jEnd] - forwardSum[j]))
                    return i;
                j++;
            }
            return -1;
        }



private void button1_Click(object sender, EventArgs e)
        {
            int[] arr = { 2, 2, 13, 4, 7, 3, 8, 12, 9, 1, 5 };
            int start = 0;
            int end = arr.Length;    
            int ret; 

            for (int i = 0; i < arr.Length; i++)
            {
                start = i;
                for (int j = 0; j < arr.Length; j++)
                {
                    end = j;
                    ret = getIndex(arr, start, arr.Length - end);
                    if (ret > 0)
                    {                       

                        MessageBox.Show(ret.ToString() + "  " + start.ToString()
                        + "  " + (arr.Length - end).ToString());
                       
                        
                    }
                    
                }
            }
       
        }

I think this can be solve in similar way as done by the merge sort.
1) for each index, call a recursive function, which will check the right & left sum(including itself).
2) maintain a counter of max sub array length ( and their indexes)
3) If the sum is not equal in this recursive function, then call the same function (itself) with the left & right subarrray.

Complexity O(nlogn)

What do u guys think??

// This code tries to find the longest subarray. 
// by comparing the myResult.sum, we can also target finding a max-sum subarray :-)
int main(void){
        int str[ARRAY_LEN] = {2,2,13,4,7,3,8,12,9,1,5};
        result myResult;
        myResult.left = -1;
        myResult.mid = -1;
        myResult.right = -1;
        myResult.sum = -1;
                
        for (int i = 1; i < ARRAY_LEN; i ++)
        {       
                int m = i-1, j=i;
                int left = str[m], right = str[j];
                while( m >= 0 && j < ARRAY_LEN ){
                        if (left  == right){
                                cout << "found equal: "<< left << endl;
                                if ( (myResult.right - myResult.left) < ( j - m)){
                                        myResult.right = j;
                                        myResult.left = m;
                                        myResult.mid = i;
                                        myResult.sum = left;
                                }       
                                m--; j++;
                                if (m >= 0 && j < ARRAY_LEN){
                                left +=str[m]; 
                                right +=str[j];
                                }
                        }else if(left < right){
                                m--;
                                left += str[m];
                        }else{  
                                j++;
                                right += str[j];
                        }       
                }       
        }       

        if(myResult.sum == -1)
                cout << "cannot find such subarray\n";
        else{
                cout << "left part: " ;
                for(int k = myResult.left; k < myResult.mid; k++)
                        cout << str[k] << " ";
                cout << " || right part: ";
                for (int k = myResult.mid; k <= myResult.right;k++)
                        cout << str[k] << " ";
        }

        cout << endl;
        return 0;

}

Hi Guys,
I think it can be done in O(n logk)
1) Create an array Sum[1.....n], where Sum[i] would hold the sum of the subarray from index 1...i ( O(n))
2) start iterating from the first element of the array
- consider first k elements.
- Do a binary search on these k elements, you can easily calculate the sum of two subarrays
first k elements having the indexes of the subarrays from array Sum[1....n] ( not the regular straightforward binary search, need to manage indexes) O(1) to calculate the sum of subarrays from Sum[] and compare
- If sums of subarrays are equal, then say true else move on to next 7 elements in the array
3) If none found, say false.
I will leave the details for you

Hi Guys,
I think it can be done in O(n logk)
1) Create an array Sum[1.....n], where Sum[i] would hold the sum of the subarray from index 1...i ( O(n))
2) start iterating from the first element of the array
- consider first k elements.
- Do a binary search on these k elements, you can easily calculate the sum of two subarrays
first k elements having the indexes of the subarrays from array Sum[1....n] ( not the regular straightforward binary search, need to manage indexes) O(1) to calculate the sum of subarrays from Sum[] and compare
- If sums of subarrays are equal, then say true else move on to next 7 elements in the array
3) If none found, say false.
I will leave the details for you

#include<stdio.h>

int main(int argc, char **argv){
int a[] = {2,3,13,4,7,3,8,12,9,1,5};
int len = sizeof(a)/sizeof(a[0]);

for(int i=0;i<len;i++){
int left=0,right=0;
int p1 = i;
int p2 = i+1;
left = left + a[p1];
right = right + a[p2];
while(p1>=0 && p2< len){
if( left == right){
printf("Left : %d, Right: %d, Center: %d \n",p1,p2,i);
break;
//return 0;
}
else if(left > right && p2 < len-1){
p2++;
right = right+ a[p2];
}
else if(left < right && p1 > 0){
p1--;
left = left + a[p1];
}
else{
//printf("Left : %d, Right: %d, Center: %d \n",p1,p2,i);
//printf("Not Possible\n");
break;
//return 0;
}
}

}
}