Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
4
of 4 vote

There is another solution that works as following:

Array = [6, -1, -3, 4, 5, 4, -15, 7] then create another array that for position i - keeps the sum of all elements from [0, i] so that we get something like

SumArray = [6, 5, 2, 6, 11, 15, 0, 7]

Now by looking in the SumArray we can see that:
1) when 0 appears at i-position it means that from the begining of the array till i-th position we have a "zero sequence".
2) if there is a matching (two the same elements, like 6, 6 in our case) then we know that from [i+1,j], where i is the first and j is the second matching, the overall change was equall to zero, so we have a "zero sequence" again.

Comment hidden because of low score. Click to expand.
0

Nice. What is the time complexity? O(n^3), right? Because there are O(n^2) such subsequences and it takes O(n) to print each.

Comment hidden because of low score. Click to expand.
2
of 8 vote

Can be done by using a dynamic programming approach. Create a matrix say A such that
A[i][j] = sum of the numbers from index i to j in the original array. and also i <= j
To build this matrix use
A[i][j] = A[i][j-1] + Input[j]
Input is the input array.
Print the i and j indices for which the value of A[i][j] = 0

Comment hidden because of low score. Click to expand.
11

This is not the best dynamic programming method.
A simple way is,
use an array sum[i] to present the sum from data[0] to data[i]. A special 0 at beginning to simplify the logic later.
Then, just find the same values in sum[].
For example,
[-1, -3, 4, 5, -2, -7]
[0, -1, -4, 0, 5, 3, -4]
There is a pair 0, that mean the range from 0 to 2.
Another pair -4, that means the range form 2 to 5.

A hash can be used to find the same value pair.
Space: O(N)
Time: O(N)

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0

@Jie
How would you find the duplicates in O(N) time and O(N) space. The duplicate elements might repeat more than twice, in which case, we need to store the indices of all the prev occurences of the element. For example, if the cummulative array were
[0, -1, -4, 0, 5, 3,0, -4]
There is a pair 0, that means the range from 0 to 2.
There is a pair 0, that means the range from 0 to 5.
There is a pair 0, that means the range from 3 to 5.

So, for this, probably we need to create a bucket kind of structure with each bucket refering to the elements of the cumm. array and each bucket containg a list of indices of occurence of the bucket element in the cumm. array. This would lead to worst case time complexity of O(n^2) {when all elements of cumm. array are same; we need to print all n_Choose_2 pairs} and O(max_value_of_sum_in_cumm_array*n) space.

Can you suggest an improvement over this approach.

Comment hidden because of low score. Click to expand.
2

Jie, there can be O(N^2) such subsequences, how do you print them all in O(N)? :)

Comment hidden because of low score. Click to expand.
0

Would it be Ω(N) and O(N^2)?
It would be better than the "traditional" Θ(N^2)...

Comment hidden because of low score. Click to expand.
0

But it's not Ω(N), because you have to go through the sum array after running the original array.

Comment hidden because of low score. Click to expand.
0

Friends,
Jie's solution can be modified to provide O(N) time complexity.

1. Each Hash table element can store Pair of 'sum' and 'list of indexes' to array of elements. Each list will have array indexes with equal sum.
3. Maintain another 'master list' of 'list of indexes with more than one item' separately. This list will be used to print sub sequences.

Comment hidden because of low score. Click to expand.
0

@sachin.sde, like Miguel said, you can't print O(n^2) things in O(n) steps. Even if printing one thing would be O(1). You just can't. :)

Comment hidden because of low score. Click to expand.
1
of 1 vote

This is a simple recursive solution. You can optimize it by storing the solution to the sub-problems (dynamic programming).

``````#include<stdio.h>
void print_zero(int a[], int n, int indx, int sum, int r[], int r_indx)
{
int i,j;
for(i=indx; i<n; i++)
{
r[r_indx]=a[i];
if(sum+a[i]==0)
{
for(j=0; j<r_indx; j++)
printf("%d ",r[j]);
printf("%d\n",a[i]);
}
print_zero(a, n, i+1, sum+a[i], r, r_indx+1);
}
}
int main()
{
int a[]={1,-1,2,-2};
int n = sizeof(a)/sizeof(a[0]);
int r[n];
print_zero(a,n,0,0,r,0);
return 0;
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

It could be done with O(n)

1) run cumulate sum on the original array
2) append [0] in font of this cum_sum_array
3) check if two item in this cum_sum_array are same (for requirement sum==0, this could be done in O(n))

Totally time spend is O(2n) = O(n)

I'm using python:

``````import numpy as np
def get_sum(array):
cumsum_array = [0] + np.cumsum(array).tolist()
key_dict = {}
for index, cum_sum in enumerate(cumsum_array):
if cum_sum not in key_dict:
key_dict[cum_sum] = index
continue
print array[key_dict[cum_sum]: index]

if __name__ == '__main__':

array = [-1, -3, 4, 5, -2, -4, 6]
get_sum(array)``````

output:

[-1, -3, 4]
[-3, 4, 5, -2, -4]
[-2, -4, 6]

Comment hidden because of low score. Click to expand.
0

One problem is that same cum_sum may appear more than twice, using a key_dict is not enough

Comment hidden because of low score. Click to expand.
0

we can modify the key_dict as key: [positions], it still could be O(n)

Comment hidden because of low score. Click to expand.
0

you should update the key_dict[cum_sum] when cum_sum may appear more than twice,like array = [-1, -3, 4, 5, -2, -4, 6,-5]

the code should be

``````def get_sum(array):
cumsum_array = [0] + np.cumsum(array).tolist()
key_dict = {}
for index, cum_sum in enumerate(cumsum_array):
if cum_sum not in key_dict:
key_dict[cum_sum] = index
continue
print array[key_dict[cum_sum]: index]
key_dict[cum_sum] = index``````

Comment hidden because of low score. Click to expand.
0

oh,oh my gosh,the

``key_dict[cum_sum] = index``

is in the loop for,,how can i change it?

Comment hidden because of low score. Click to expand.
2

Your solution won't show all options for [-1,-3,4,-1,1,-1,5]. @fword solution neither.

``````def get_sum(array):
cumsum_array = [0] + np.cumsum(array).tolist()
key_dict = {}
for index, cum_sum in enumerate(cumsum_array):
if cum_sum not in key_dict:
key_dict[cum_sum] = [index]
continue

for i,v in enumerate(key_dict[cum_sum]):
print array[v: index]
key_dict[cum_sum].append(index)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````void printTriplet(const int a[], int n)
{
int result[n][n] = {0};

for( int x = 0; x <= n ; x ++ )
{
for( int y = 0; y < n; y ++ )
result[x][y] = MAXINT;
}

for( int i = 0; i < n; i ++ )
{
for( int x = 0; x <= i ; x ++ )
{
for( int y = i; y < n; y ++ )
{
if( result[x][y] == MAXINT )
result[x][y] = 0;

result[x][y] += a[i];
}
}
}

for( int x = 0; x <= n ; x ++ )
{
for( int y = 0; y < n; y ++ )
if( result[x][y] == 0 )
print( a, x, y );
}

}

void print( int a[], int x, int y )
{
printf("Triplet: ");
for( int i = x; i <= y; i++ )
{
printf("%d ", a[i] );
}
printf("\n");
}``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

If the problem is looking for subarrays, then it can be solved by divide and conquer;

Split the problem into three subproblems:
1. All subarrays in array A[0...n/2 - 1] that sum to 0
2. All subarrays containing element a[n/2] that sum to 0
3. All subarrays in array A[n/2 + 1..n] that sum to 0

The time complexity is O(n (logn)^2)
T(n) = 2T(n/2) + nlogn

Space complexity is O(n)

Otherwise it is subset sum problem.

Comment hidden because of low score. Click to expand.
0

``````void print_subarray(int* data, int start, int end) {
for (int i = start; i <= end; i++) {
cout << data[i];
if (i < end) { cout << ", "; }
}
cout << endl;
return;
}

void find_subarray_partial(int* data, int* buffer, int* indexes, int start, int end) {
if (start > end) { return; }
if (start == end) {
if (data[start] == 0) {
print_subarray(data, start, start);
}
return;
}
int middle = start + (end - start) / 2;

find_subarray_partial(data, start, middle - 1);
find_subarray_partial(data, middle + 1, end);

// Sub problem in which data[middle] must be part of the subarray

// 1. Calculate the sum around data[middle]
buffer[middle] = data[middle];
int sum = data[middle];
for (int i = middle - 1; i >= start; i--) {
sum += data[i];
buffer[i] = sum;
}
sum = data[middle];
for (int i = middle + 1; i <= end; i++) {
sum += data[i];
buffer[i] = sum;
}

// 2. Sort the sums on left and right side of data[middle] separately, and record indexes before sort. Insertion sort used here for simplicity but real implementation should be replaced by a sorting algorithm with complexity O(nlogn)

for (int i = start; i <= end; i++) {
indexes[i] = i;
}
for (int i = start; i < middle; i++) {
for (int j = start; j < i; j++) {
if (buffer[i] < buffer[j]) {
swap(buffer[i], buffer[j]);
swap(indexes[i], index[j]);
}
}
}

for (int i = middle + 1; i <= end; i++) {
for (int j = middle + 1; j < i; j++) {
if (buffer[i] < buffer[j]) {
swap(buffer[i], buffer[j]);
swap(indexes[i], index[j]);
}
}
}

// 3. Get pairs from left and right side of middle whose sums add up to -data[middle]
int left = start;
int right = end;
int target = -data[middle];
while (left < middle && right > middle) {
int sum = buffer[left] + buffer[right];
if (sum == target) {
// Found a pair, output the sequence
print_subarray(data, indexes[left], indexes[right]);
left++;
right++;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}

void find_subarray(int* data, int* indexes, int size) {
int* buffer = new int[size];
int* indexes = new int[size];
find_subarray_partial(data, buffer, 0, size - 1);
delete [] buffer;
delete [] indexes;
}``````

Comment hidden because of low score. Click to expand.
4

How is order N log N and if the given array contains all Zeros u must print N*(N-1)/2 intervals ?

Comment hidden because of low score. Click to expand.
0

Exactly, you can't beat O(N^2) in the worst case.

Comment hidden because of low score. Click to expand.
0

You're right, the worst case complexity is O(N^2), and i made some mistakes in step 3. after finding a target.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

What SUBSET SUM problem? Ridiculous. Do you even what that is?

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int main()
{
int a[] = {6, -1, -3, 4, 5, 4, -15, 7};
int N = 8;

for(int i = 0; i < N; i++)
{
int sum = 0;
for(int j = i; j < N; j++)
{
sum += a[j];
if(sum == 0)
{
for(int k = i; k <= j; k++)
printf("%d, ", a[k]);
printf("\b\b  \n");
}
}
}

return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think this question can be solved by one pass traversal.
Use an additional array sum which sum[i] represents sum from data[0] to data[i].
If we find two elements in array sum that they have the same value, for example, sum[i] = sum[j]
then we can sure that the sum of continuous sequence data[i+1] to data[j] is zero.
Note that there maybe an exception. If any sum[i]`s value is zero, that means the sum of sequence from data[0] to data[i] is zero

For example
input is -1, -3, 4, 5, 4
sum is -1, -4, 0, 5,9
sum[2] is zero that means data[0] + data[1] + data[2] = 0

input is 1,3,5,7,9,-2,2
sum is 1 4 9 16 25 23 25
sum[4] = sum[6], that means data[5] + data[6] = 0

Time complexity is O(n)
Space complexity is O(n)

Comment hidden because of low score. Click to expand.
0
of 0 vote

//Author : A.NAsimunni
//Cse student
#include<stdio.h>
main()
{
int n;
printf("\n\tEnter size of an array : ");
scanf("%d",&n);
int a[n];int i;
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
int j=0,s=0,m;
int t[n];int k=0;

for(i=0;i<n;i++)
{
s=0;
k=0;t[k]=a[i];s=s+a[i];k=k+1;

for(j=i+1;j<n;j++)
{
t[k]=a[j];k=k+1;
s=s+a[j];
if(s==0)
for(m=0;m<k;m++){printf(" %d ",t[m]);}
}
else
{;}
}
}
printf("\n\n");
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

//Author : A.NAsimunni
//Cse student
#include<stdio.h>
main()
{
int n;
printf("\n\tEnter size of an array : ");
scanf("%d",&n);
int a[n];int i;
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
int j=0,s=0,m;
int t[n];int k=0;

for(i=0;i<n;i++)
{
s=0;
k=0;t[k]=a[i];s=s+a[i];k=k+1;

for(j=i+1;j<n;j++)
{
t[k]=a[j];k=k+1;
s=s+a[j];
if(s==0)
for(m=0;m<k;m++){printf(" %d ",t[m]);}
}
else
{;}
}

}
printf("\n\t\tThank you\n");
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Another approach by using maps. Assume we keep track of cumulative sum of array. If there is a subsequence starting from index n1 to n2 summing to zero, then the cumulative sum is equal at n1 and n2. Just need to remember the locations.

``````map<int, vector<int>> locs;
int cs = 0;
locs[0]=0;

for (int i = 0; i < N; i++)
{
cs += arr[i];
locs[cs].push_back(i);
}
/// now go over map to identify subsequence
for (auto it = locs.begin(); it != locs.end(); ++it)
{
List_sequences(it->second);
}``````

``list_sequences``

simply prints sub sequences based on starting indices. For instances, the cumulative sum meets value "2" at indices 4, 8, 120, the there are three sub sequences: 4-8, 8-120, 4-120.

Time : O(N + M)
Space: O(N)
M = Total number of subsequences

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int n,i,a[10001];
cin>>n;
for(i=0;i<n;i++)cin>>a[i];
sort(a,a+n);
for(i=0;i<n;i++)
{
if(a[i]<=0)
{
int l=i+1,r=n-1,k=-a[i];
while(l<n && r<n && l<r)
{
if(a[l]+a[r]>k)
{
r--;
}
else if(a[l]+a[r]<k)
{
l++;
}
else
{
cout<<a[i]<<" "<<a[l]<<" "<<a[r]<<endl;
l++;
r--;
}
}
}
}
cin>>n;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int n,i,a[10001];
cin>>n;
for(i=0;i<n;i++)cin>>a[i];
sort(a,a+n);
for(i=0;i<n;i++)
{
if(a[i]<=0)
{
int l=i+1,r=n-1,k=-a[i];
while(l<n && r<n && l<r)
{
if(a[l]+a[r]>k)
{
r--;
}
else if(a[l]+a[r]<k)
{
l++;
}
else
{
cout<<a[i]<<" "<<a[l]<<" "<<a[r]<<endl;
l++;
r--;
}
}
}
}
cin>>n;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct range{int x,y;};
struct xyz{int su,in;}s[100001];
bool c(const xyz &l,const xyz &r){if(l.su==r.su)return(l.in<r.in);return(l.su<r.su);}
vector<range> ra;
int main()
{
int n,a[100001],i,j;
cin>>n;
for(i=1;i<=n;i++)cin>>a[i];
for(i=1;i<=n;i++){s[i].su=s[i-1].su+a[i];s[i].in=i;}
//for(i=1;i<=n;i++)cout<<s[i].su<<" ";
sort(s+1,s+n+1,c);
//for(i=1;i<=n;i++)cout<<s[i].su<<" ";
cout<<endl;
for(i=1;i<=n;i++)
{
if(s[i].su==0)
{
ra.push_back((range){1,s[i].in});
}
j=i+1;
while(s[j].su==s[i].su && j<=n)
{
ra.push_back((range){s[i].in+1,s[j].in});
j++;
}
}
for(i=0;i<ra.size();i++)
{
for(j=ra[i].x;j<=ra[i].y;j++)
{
cout<<a[j]<<" ";
}
cout<<endl;
}
cin>>n;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Python Code:

startend = {}

def getZeroSubsFromIndex(array, startIndex):
sum = 0
for i in range(startIndex, len(array)):
sum += array[i]
if sum == 0:
if startIndex not in startend:
startend[startIndex] = [i]
else:
startend[startIndex].append(i)

def getAllZeroSubs(array):
for i in range(len(array)):
getZeroSubsFromIndex(array, i)
print startend

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int countSubArray(int A[], int n)
{
map<int, int> accumCountMap;
accumCountMap[0] = 1;
int sum = 0;
for (int i = 0; i < n; i++)
{
sum += A[i];
if (accumCountMap.find(sum) == accumCountMap.end())
accumCountMap[sum] = 1;
else
accumCountMap[sum]++;
}

int cnt = 0;
for (auto iter = accumCountMap.begin(); iter != accumCountMap.end(); iter++)
{
int val = iter->second;
if (val > 1)
cnt += val * (val - 1) / 2;
}
return cnt;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static List<List<Integer>> zeroSumSubsequence(final List<Integer> list) {
if (list.isEmpty()) {
return Collections.emptyList();
}
List<List<Integer>> result = new ArrayList<>();
final List<Integer> sum = new ArrayList<>(list);
for (int i=1; i<sum.size(); ++i) {
sum.set(i, sum.get(i) + sum.get(i-1));
}
for (int i=0; i<sum.size() - 1; ++i) {
for (int j=i+1; j<sum.size(); ++j) {
if (sum.get(j) - sum.get(i) == 0) {
}
}
}
return result;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

This can be done in one pass. Take a hash table(say h) with a key (0) and value (-1). Add one by one element (i is incerementing) from the array to sum (say sum) and also add the sum as key into the hashtable(h) with value as i (current counter). Before adding to hashtable(h),each time check, if a key already exists in the hashtable with the cumulative sum. If exists, means zero sum formed from h(sum)+1 to current pointer(i), so print them. if the sum not exist in h, simply add it (need to update h(sum) with current i, even it found, so that we can track next occurrence of that sum).
Here is the code:

``````void PrintCum_Sum(int[] a)
{
Hashtable h = new Hashtable();
int sum=0;
for (int I=0;i<a.length;a++)
{
sum+=a[i];
if (h[sum].exists())
{
Print ("Below elements form sum 0");
for(int j=h(sum)+1;j<=i; j++)
print(a[j];
}
h(sum) = i; // update with current pointer, to compare for next repetition
}
}``````

Comment hidden because of low score. Click to expand.
0

small corrections :(.

``````void PrintCum_Sum(int[] a)
{
Hashtable h = new Hashtable();
int sum=0;
for (int i=0;i<a.length;a++)
{
sum+=a[i];
if (h[sum].exists())
{
Print ("Below elements form sum 0");
for(int j=h(sum)+1;j<=i; j++)
print(a[j];
h[sum] = i; // update with current pointer, to compare for next repetition
}
else
{
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class Main {

public static final void main(String[] args) {
printSubsequence(new int[] {-1, -3, 4, 5, 4}, 0);
}

private static void printSubsequence(int[] array, int sumTotalToFind) {
for(int i = 0, arrLen = array.length; i < arrLen; i++) {
int sum = 0;
for(int j = i; j < arrLen; j++) {
sum += array[j];

if(sum == sumTotalToFind) {
System.out.println(list);
}
}

list.clear();
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Folks.... this is the situation.
Subarray summing to K is the problem.
There are two distinct subcases:

1) If arrays elements are assumed to be nonnegative, then you can do a slick O(N) solution

2) If array elements can be negative too, you can't beat O(N^2) ... last time I tried I couldn't :P

Comment hidden because of low score. Click to expand.
0
of 0 vote

static int[] input_array = {-1, -3, 4, 5, 7};
static int l=input_array.length;
static int total;
static int first;

{
for (int i=0; i<l-2; i++)
{
first = input_array[i];
total = input_array[i]+input_array[i+1]+input_array[i+2];
//System.out.println("comparing " + first +" with:" + input_array[i+1]+ " & " +input_array[i+2]);
if (total==0)
{
System.out.println(first +" AND " + input_array[i+1]+ " AND " +input_array[i+2]);
}

}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

My decision on python:

``````def find_cont(numbers):
length = len(numbers)
i = 0
while i < length:
def find_sum(numbers):
if not numbers:
return
sum = int(numbers[0])
values = [sum]
if sum == 0:
print values
for num in numbers[1:]:
sum += int(num)
values.append(num)
if sum == 0:
print values
find_sum(numbers[i+1:])
i += 1``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution in JavaScript - not sure about the time complexity.

``````(function(){
window.subsetToZero = function(arr){
var i,
j,
k,
subsets = [],
sums = [];

for (i=0; i < arr.length; i++){
sums.push([0]);
for (j=0; j < sums.length; j++){
for (k=0; k <= i; k++){
sums[j][k] +=  arr[i];
if (sums[j][k] === 0){
subsets.push([j, i]);
}
}
}
}
return subsets;
}
})();``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void printZero(int[] input)
{
int[] sum = new int[input.Length];
int currSum = 0;
for (int i = 0; i < input.Length; i++)
{
currSum += input[i];
sum[i] = currSum;
}

List<KeyValuePair<int, int>> storePairs = new List<KeyValuePair<int, int>>();
Hashtable map = new Hashtable();

for (int i = 0; i < input.Length; i++)
{
if (sum[i] == 0)
{
KeyValuePair<int,int> kvp = new KeyValuePair<int,int>(0, i);
}

if (map.ContainsKey(sum[i]) == false)
{
}
else
{
object key = (object)sum[i];
int startIndex = (int)map[key];
KeyValuePair<int, int> kvp = new KeyValuePair<int, int>(startIndex + 1, i);
}
}

foreach(KeyValuePair<int,int> kvp in storePairs)
{
int startIndex = kvp.Key;
int endIndex = kvp.Value;
for (int j = startIndex; j <= endIndex; j++)
Console.Write(input[j] + " ");

Console.WriteLine();
}
}

static void Main(string[] args)
{
printZero(new int[] { -1, -2, 4, -1, 0, 4, 2, 3, -5 });
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote
Solution in one pass, without recursion and without additional array to store the sums. {{{import java.util.HashMap; import java.util.HashSet; public class SumZeroContinuousSequences { public static void printSumZeroContSeq(int[] arr) { HashMap<Integer, HashSet<Integer>> hmap = new HashMap<Integer, HashSet<Integer>>(); int currentSum = 0; HashSet<Integer> hset = new HashSet<Integer>(); hset.add(-1); hmap.put(0, hset); for (int i = 0; i < arr.length; i++) { currentSum += arr[i]; if(!hmap.containsKey(currentSum)) { hset = new HashSet<Integer>(); hset.add(i); hmap.put(currentSum, hset); } else { hset = hmap.get(currentSum); for (Integer j : hset) { printSeq(arr, j, i); } hset.add(i); } } } private static void printSeq(int[] arr, int j, int i) { for (int k = j+1; k < i; k++) { System.out.print(arr[k] + ", "); } System.out.println(arr[i]); } public static void main(String[] args) { int[] arr = {-1, -3, 4, 5, 4, -4, -5}; printSumZeroContSeq(arr); } }}
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution in one pass, without recursion and without additional array to store the sums.

``````import java.util.HashMap;
import java.util.HashSet;

public class SumZeroContinuousSequences {

public static void printSumZeroContSeq(int[] arr) {
HashMap<Integer, HashSet<Integer>> hmap = new HashMap<Integer, HashSet<Integer>>();
int currentSum = 0;
HashSet<Integer> hset = new HashSet<Integer>();
hmap.put(0, hset);
for (int i = 0; i < arr.length; i++) {
currentSum += arr[i];
if(!hmap.containsKey(currentSum)) {
hset = new HashSet<Integer>();
hmap.put(currentSum, hset);
} else {
hset = hmap.get(currentSum);
for (Integer j : hset) {
printSeq(arr, j, i);
}
}
}
}

private static void printSeq(int[] arr, int j, int i) {
for (int k = j+1; k < i; k++) {
System.out.print(arr[k] + ", ");
}
System.out.println(arr[i]);
}

public static void main(String[] args) {
int[] arr = {-1, -3, 4, 5, 4, -4, -5};
printSumZeroContSeq(arr);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Two step process:
1. Figure out the aggregate sum
2. Find the repeated sums (indicating the numbers in between summed to 0).

``````def get_zero_sum_subsets_smart(integer_set):
integer_sum_set = [0 for x in xrange(0, len(integer_set) + 1)]
integer_map = {}

subsets = []
subset_lists = []

# calculate the cumilative sums
for i in xrange(0, len(integer_set)):
integer_sum_set[i + 1] = integer_sum_set[i] + integer_set[i]

# create a hash table for the sums and find duplicates
for i in xrange(0, len(integer_sum_set)):
sum = integer_sum_set[i]

if sum not in integer_map:
integer_map[sum] = [i]
else:
for start in integer_map[sum]: subsets.append((start, i))
integer_map[sum].append(i)

for start, end in subsets:
subset_lists.append(integer_set[start:end])

return subset_lists

print get_zero_sum_subsets_smart([-1, 1, -1, -3, 4, 5])``````

Comment hidden because of low score. Click to expand.
-1
of 3 vote

This is the classic subset sum problem, which is asked here many many many times before and is NP-complete problem. You can check out en.wikipedia.org/wiki/Subset_sum_problem for more info.

Comment hidden because of low score. Click to expand.
1
of 1 vote

This is not a subset sum problem. It is a subsequence sum problem.

That said, elements should be continuous in the array whose sum is 0.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Mukesh: You should make that clear in the problem, since subsequence does not need the elements to be continuous in the array. [1, 2, 4] is a subsequence of [1, 2, 3, 4]

Comment hidden because of low score. Click to expand.
0

PC, the problem statement says clearly "continuous subsequences"

Comment hidden because of low score. Click to expand.
1
of 1 vote

Miguel Oliveira : The problem statement has been updated. The continuous part was not mentioned before. It was only " subsequence "

Comment hidden because of low score. Click to expand.
0

@Up The original problem was subset sum and now they added "continuous" part! I've seen this a lot of times, where people keep changing the problem statement after posting.

Comment hidden because of low score. Click to expand.
0

Thats right. I added "continuous" later to avoid any further confusion.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

So, if we are talking about "continuous subsequences", then we just need to traverse the array once, add a[i], a[i+1], a[i+2], and print a[i], a[i+1], a[i+2] whenever the sum is 0, right? Am I missing something here?

``````static int[] input_array = {-1, -3, 4, 5, 7};
static int l=input_array.length;
static int total;
static int first;

{
for (int i=0; i<l-2; i++)
{
first = input_array[i];
total = input_array[i]+input_array[i+1]+input_array[i+2];
//System.out.println("comparing " + first +" with:" + input_array[i+1]+ " & " +input_array[i+2]);
if (total==0)
{
System.out.println(first +" AND " + input_array[i+1]+ " AND " +input_array[i+2]);
}

}
}``````

Comment hidden because of low score. Click to expand.
0

@AB

Subsequence need not be of only 3 elements. It can be of 1, 2, 3, 4 ... any number of consecutive elements.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.