CareerCup

Algo:

1. iterate through the array once, and take the sum from 0 to every other index of the array.
2. If any sum is zero, the subarray from 0 to that index is the first such subarray.
else
3. In the sum, if any two numbers are same, then the subarray between those two index is the first such subarray to have a sum zero.

The algo works o(n). Two iterations are required.

1. From the input array A, create a new array B which contains sum from the beginning till the current position.
5 -5 4 2 1 -3 -4 7 will become 5 0 4 6 7 -4 0 7

2. Now, take a hash map HM as <int,pair(int,int)> and put all the values in following order.
a) If no current key is present, put the key with value (i,-1) this means, i is the current index, and 0 signifies its not close yet.
b) If key is present, update value as (i,j), i is the first instance when we write it, and j is whenever we will find it again in our array.
c) For key 0, its a special case. As an empty subarray is also have a sum 0. Thus, if any 0 occurs in B, we will say from start till the current position where 0 is lying we have got a sub array. So, for 0, wherever we get last 0 in array, we will take that position.

3. Example
a) For first element 5, we will put as 5 --> (0,-1)
b) For second element 0, will put as 0 --> (0, 1)
c) For 4, we will put as 4 --> (2,-1)
d) For 6, we will put as 6 --> (3,-1)
e) For 7, we will put as 7 --> (4,-1)
f) For -4, we will put as -4 --> (5,-1)
g) For 0, we will put as 0 --> (0,6)
h) For 4, we will put as 4 --> (4,7)

4. Traverse through this hash map and find max of (j-i). In this case its 6 coming from (0,6), thus, print array from 0 to 6.

Hope my logic is clear.

It will run in O(n) time with O(n) space. This O(n) space can be saved, if we can destroy the input array which personally I dont want.

Here is O(N) time and O(N) space algorithm.

public static int[] getSubarr( int[] arr ){
				
		Map<Integer, Integer> previousSums = new HashMap<>();
		
		int sum = 0;
		
		for(int i = 0; i < arr.length; i++ ){
						
			sum += arr[i];			
			
			if( sum == 0 ){
				return Arrays.copyOfRange(arr, 0, i+1);
			}
			
			if( previousSums.containsKey(sum) ){				
				int from = previousSums.get(sum) + 1;
				int to = i;				
				return Arrays.copyOfRange(arr, from, to+1);
			}
			
			previousSums.put( sum, i );
		}
		
		return null;
	}

I think this can be solves easily with Dynamic Programming

which one of them is the first subarray with 0 sum in the given array : -1,2,8,7,-11,-6,1,8,-9,7,9
(a) -1,2,8,7,-11,-6,1
(b) 2,8,7,-11,-6

(a)

its simple....find a subarray with sum=0. I think everyone knows the code for finding subarray for given sum.

You can do this with 0(n) complexity as well

idea:-
1. As you need sum =0, so take one map<int ,int>
2. check whether (-sum ) is present 
      if (true)    store the index in some variable.
      else   keep the (-sum) in the map.
3. After getting the index  where sum =0;
4. read array backwards from that index and get the index where sum =0 (maintain sum ...);
5. You will get the starting and ending index both. Between them is your answer.
 it handles  -1,2,8,7,-11,-6,1,8,-9,7,9 this case also. ..:-)

Posting my approach;
Consider the below array;
-1,2,8,7,-11,4,12

Now construct the sum array starting from 0-n,
ie
-1,1,9,16,5,9,21
Now the subarray is the first repeating integer .In this case starting from first index of '9' to last '9' .
Basically since the value is 0, you just need to figure out the first occurrence where the sum of elements becomes the same.

Please let me know any comments.

int[] array = {1, 2, -3, 4, 5, 6};
      //System.out.println(array.length);
      for (int i = 0; i < array.length; i++) {
    	  //System.out.println("I: " + i + "/n");
      	for (int u = i + 1; u < array.length; u++) {
      		//System.out.println("U: " + u + "/n");
      		int finale = 0;
      		for (int a = i; a <= u; a++) {
      			finale += array[a];
      		}
      		if (finale == 0) {
      			System.out.println("GOTOVO");
      		}
      	}
      };

Another approach: (rough code)

sum=0; I=0,J=0;      //I,J will contain sub-sequence indices.
for(int  i=0;i< n;i++)         //n=length of array.
{
sum += arr[i];           //arr is given array.
	if(HashTable(sum).Exists)     //HashTable is any hash table. sum is key and i(index) is value.
	{
		I=HashTable.GetValue(sum) +1;
		J=i;
		break;
	}
	else
	{
		Hash.AddNewEntry(sum,i);       
	}
}

How about this approach? I will pass pos and subSum is 0 initially

bool findSubSum(int[] arr, int pos, int subSum)
{
if (pos == arr.Length)
return false;

subSum -= arr[pos];

if (subSum == 0)
return true;

return findSubSum(arr, pos + 1, subSum);
}

#include<stdio.h>


int a[]={8,-9,11,-4,31,-1,2,-3,10,1,-3,4,7,-12,34,-12,-7,19};

int main()
{
	int i,j;
	int sum1,sum2;
	int len;
	
	len=sizeof(a)/sizeof(a[0]);
	sum1=a[0]+a[1];
	if(sum1==0)
	{
		printf("low=0 high=1\n");
		return 0;
	}

	

	for(i=2;i<len;i++)
	{
		sum2=0;
		sum1+=a[i];
		if(sum1==0)
		{
			printf("low=0 high=%d\n",i);
			return 0;
		}
		else
		{
			for(j=0;j<i;j++)
			{
				sum2+=a[j];
				if(sum1-sum2==0)
				{
					printf("low=%d high=%d\n",j+1,i);
					return 0;
				}
			}
		}
	}

	printf("not found\n");
	return 0;
}

for(i=0;i<n;i++)
{
sum=0;
for(j=i;j<n;j++)
{
      sum+=a[j];
      if(sum==0)
      {
         printf("sub array with sum zero is start at %d and ends at %d ",i,j);
break;
}
}
}

We keep track of the sum so far and current sum, if the current sum brings us closer to zero, we update the bounds, if not then we keep iterating.

bool findSumZero( int arr[], int n )
{
	int sum_so_far = INT_MAX;
	int current_sum = 0;
	int start = 0;
	int end = 0;
	bool found = false;

	for (int i = 0; i < n; i++)
	{
		if (arr[i] == 0)
		{
			found = true;
			start = i;
			end = i;
			cout << start << " " << end << endl;
			return true;
		}
		
		if (current_sum + arr[i] == 0)
		{
			end = i;
			cout << start << " " << end << endl;
			return true;
		}

		if (current_sum + arr[i]  <  sum_so_far && sum_so_far > 0)
		{
			// want to reduce the sum to bring it closer to zero
			end = i;
			sum_so_far = current_sum + arr[i];
			current_sum += arr[i];
		}
		else
		{
			if (current_sum + arr[i]  >  sum_so_far && sum_so_far < 0 )
			{
				// want to increase the sum to bring it closer to zero
				end = i;
				sum_so_far = current_sum + arr[i];
				current_sum += arr[i];
			}
			else
			{
				start = i;
				sum_so_far = arr[i];
				current_sum = arr[i];
			}
		}
	}
	return false;
}