Click here to Skip to main content
15,867,568 members
Please Sign up or sign in to vote.
1.00/5 (4 votes)
I have created a program which that takes as input an array of positive and negative numbers (0 excluded) and return those items from the array whose sum is 0. If no such items exist return, then return “No Elements found”. Here I have written separate functions for twoSum, threeSUM, fourSum... but I want to have general function which will check for nSum (n is the number of elements of array)
e.g. In this list [-4, -3, -2, -1, 10], it should return -4, -3, -2, -1 and 10 there are 5 elements whose sum is 0. I am sharing my code. I have written in Python, but code in C/C++ is also welcomed. So please help.

What I have tried:

```
def twoSum(arr,n,x,lp,rp):
    while lp<rp:
        if arr[lp] + arr[rp] == x:
            return True,arr[lp],arr[rp]
        elif arr[lp] + arr[rp] < x:
            lp+=1
        else:
            rp-=1
    return False,0,0

def threeSum(arr,n,x,firstIndex):
    for i in range(firstIndex,n-2):
        check,a,b = twoSum(arr,n,x-arr[i],i+1,n-1)
        if check:
            return True,arr[i],a,b
    return False,0,0,0
            
def finding_numbers(arr, n):
    if arr[0]<0:
        check,a,b = twoSum(arr,n,0,0,n-1)
        if check:
            return a,b
        
        check,a,b,c = threeSum(arr,n,0,0)
        if check:
            return a,b,c
          
        for i in range(n-3):
            check,a,b,c = threeSum(arr,n,-arr[i],i+1)
            if check:
                return arr[i],a,b,c
    return 'No Elements found'

finding_numbers(array, n)
```
Posted
Updated 15-Jan-23 20:55pm
Comments
Graeme_Grant 15-Jan-23 4:54am    
I don't see any question other than "can you show us yours?".

Does it work? Does it throw errors and where? What difficulties are you having?
Dakush 15-Jan-23 5:11am    
Actually the problem is, say the number of elements in array, n=10. I have to find those elements of array whose sum is zero.
I am thinking of the approach:
1. Find if any two elements make sum 0. If found, then return those elements, otherwise move to next step. (twoSum)
2. Then find if any three elements make sum 0. If found, then return those elements, otherwise move to next step. (threeSum)
3. Then find if any four elements make sum 0. If found, then return those elements, otherwise move to next step. (fourSum)
.
.
n. Then find if all the elements make sum 0. If found, then return those elements, otherwise return no element found. (nSum)
In this case, I have to write separate function for each step. So if n=10, I have to write n fuctions.
I am asking for a general function which will find elements for any value of n.
Graeme_Grant 15-Jan-23 5:44am    
So you're asking us to write your code for you?
Dakush 15-Jan-23 5:11am    
Actually the problem is, say the number of elements in array, n=10. I have to find those elements of array whose sum is zero.
I am thinking of the approach:
1. Find if any two elements make sum 0. If found, then return those elements, otherwise move to next step. (twoSum)
2. Then find if any three elements make sum 0. If found, then return those elements, otherwise move to next step. (threeSum)
3. Then find if any four elements make sum 0. If found, then return those elements, otherwise move to next step. (fourSum)
.
.
n. Then find if all the elements make sum 0. If found, then return those elements, otherwise return no element found. (nSum)
In this case, I have to write separate function for each step. So if n=10, I have to write n fuctions.
I am asking for a general function which will find elements for any value of n.

This is basically a combinations problem: you need to check every possible "group" of numbers from a set util the sum of those numbers is zero.

So if you have a group of numbers a,b, and c, the combinations are
a
b
c
a, b
a, c
b, c
a, b, c
(Because addition is commutative the you can ignore "b, a", "c, a", "b, a, c" and so on) Needless to say, the number of combinations grows exponentially as the number of values increases: for 4 values there are 15 combinations, and so on.

So start here: combinations algorithm - Google Search[^] and see what you can work out.
 
Share this answer
 
Comments
CPallini 15-Jan-23 6:25am    
5.
First analyze the problem, play with it.
For any array of size N, there is 2^N possible subarrays, minus 1 because you want to use at least 1 element of the array.
It is a brute force attack because you need to check all combinations.
C++
You have an array of size N
A0 A1 A2 A3 A4 binary  Dec
1  0  0  0  0  0b00001 1
0  1  0  0  0  0b00010 2
1  1  0  0  0  0b00011 3
0  0  1  0  0  0b00100 4
1  0  1  0  0  0b00101 5
0  1  1  0  0  0b00110 6
...

As you can see, one need to just list values from 1 to 2^N-1.
In binary form, each bit tells if an element of array is used or not.
 
Share this answer
 
Comments
0x01AA 15-Jan-23 9:27am    
Very unconventional representation of binary numbers from left to right (A0 ... A4) :-)
But the information is correct. 5.
Patrice T 15-Jan-23 10:19am    
I know :)
It is to match array elements positions with bits position.
Graeme_Grant 15-Jan-23 11:29am    
This is a variation on the "Largest Sum Contiguous Subarray" which can have a Time Complexity of O(N). I would generate a proof but I don't want to do his homework for him... This should be enough of a tip to point him in a direction.
CPallini 15-Jan-23 13:07pm    
Very nice.
5.
Patrice T 15-Jan-23 16:33pm    
Thank you
With a recursive call, the search for a suitable combination could be done with a few lines.
C++
void Combination_int(std::vector<int>& input, std::vector<int>& combination,
       int start, int end, int index, int r)
{
	if (index == r) {
		// TODO: Check the Combination
		}
		return;
	}
	for (int i = start; i <= end && end - i + 1 >= r - index; i++) {
		combination[index] = input[i];
		Combination_int(input, combination, i + 1, end, index + 1, r);
	}
}

The call will look like this :
C++
Combination_int(inputs, combinations, 0, n - 1, 0, r);

The parameters are as follows :
inputs: Vector with all given values
n : Number of elements of the input vector
r : number of elements of the combination to be checked
combinations : an empty field with size r
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900