CareerCup

Solution was given by someone in the earlier posts like this:
Take another array of same size, at each position, fill in sum from ele at index 0 upto that position.
For example:
sum[0] = a[0]
sum[1] = sum[0] + {a[1]}
sum[2] = sum[1] + {a[2]}
and so on.

Now you want to find a duplicate value in this array. For that purpose, sort this 'sum' array. Find two consecutive values in this array which have same value.
For example:
sum[4] and sum[7] (in previous unsorted array, not the sorted one) may have same value, or any others.
Since these two values are same, it means sum of values between a[4] and a[7] should sum to 0. Precisely, (a[5] + a[6] + a[7]) should sum to zero here.

Thats it.
Complexity:
Time: O(n),
Space: O(n).


And someone suggested to check if any of the sum[i]s is also zero along with differences.. And this is true!


Now, can someone suggest a solution to the problem if the above question is extended asking you to find the longest(but not any) such slice??

Longest can be accomplished by using the index as the secondary sort key and looking at only the first and last index for each group of sums.

@anonymous Now, take some medicine.. :D
The idea of sorting sum[] is actually given by someone to find the duplicates(i.e. "Find two consecutive values in this array which have same value" in the given explanation)
Now this can be achieved using a hashmap with O(n).. So, the time is given as O(n)

int main()
{
int a[6] = {1,2,-1,-2,3,-3};
int start =0, end=0, sum = 0;

for(int i=0;i<6;i++)
{

if(i==0)
sum = sum+a[i];
else
{
sum = sum+a[i];
end = i;

if(sum == 0)
{
cout<<"before i = "<<i<<endl;
while(start <=end)
{
cout<<a[start];
start++;
}
cout<<endl;
i++;
cout<<"after i = "<<i<<endl;
sum = a[i];
start = end = i;
}
}
}
system("PAUSE");
return 0;
}

int main()
{
int arr[6] = {1,2,-2,-1,3,-3};
int sum1 = 0;
int sum2 = arr[1];
int start1 = 0;
int start2 = 1;

for(int i =0;i<6;i++)
{
sum1 = sum1 + arr[i];
sum2 = sum2 + arr[i+2];
if(sum1 == 0)
{

while(start1<=i)
{

cout<<arr[start1]<<"\t";
start1++;
}
cout<<endl;
//start1++;
}
if(sum2 == 0 && i!=5)
{

while(start2<=i+2)
{

cout<<arr[start2]<<"\t";
start2++;
}
cout<<endl;
//start2++;
}
}

}

This is subset-sum problem. Dynamic Programming.

I hope this one works

sum=0;
map[0]=-1;
for i=0 to n 
sum+=a[i]
if(exists(map[sum]))  
  return map[sum],i
else  
  map[sum]=i

int zeroSumSubArray(int A[], int n, int *start, int *end)
{
	int cSum[n]; // cumulative sum array
	cSum[0] = A[0];
	for(int i=1; i<n; i++ )
	{
		cSum[i] = cSum[i-1] + A[i];

		if( cSum[i] == 0)
		{
			*start = 0;
			*end = i;
			return 1; //found slice sub array
		}
		else
		{
			int index = hashFind(cSum[i]);
			if( index == -1)
			{
				hashAdd(cSum[i]); // element does not find in hash table
			}
			else
			{
				*start = index + 1;
				*end = i;
				return 1;
			}
		}
	}
	return 1;
}

Time & space complexities O(n);

For solving the above algorithm we will need to use the concept of multimap and hashmap we will traverse the array and will keep summing the integers in the array and as soon as we find that the sum exists in the hashmap we will check for the number and then, if found we will print the subarray because the logic is that if there is a number from before in the hashmap then, there exist at least one subarray whose sum = 0.

Implementation:

void findsubarray(int arr[], int n){
	int sum = 0;
	unordered_multimap<int, int> map;
	map.insert(pair<int, int>(0, -1));
	for(int i = 0; i < n; i++){
		sum += arr[i];
		if(map.find(sum) != map.end()){
			auto it = map.find(sum);
			for(it = map.begin(); it != map.end(); it++)
				if(it->first == sum)
					cout<<it->first + 1<<" "<<i;
		}
		map.insert(pair<int, int>(sum, i));
	}
}