CareerCup

bool IsPossible(int arr[], int n, int sum)
{
	if (n == 1) return sum == abs(arr[0]);
	return IsPossible(arr, n-1,  sum + arr[n-1]) || IsPossible(arr, n-1,  sum - arr[n-1]);

}
int main()
{
    int arr[]={1,2,3};
	printf(IsPossible(arr, 3, 0) ? "yes\n" : "no\n");

    int arr2[]={3,6,2};
	printf(IsPossible(arr2, 3, 0) ? "yes\n" : "no\n");

    return 0;
}

DP problem (partition problem)
Recurrence relation:
Assume P[i,j] be true if a subset of {a[1], a[2]..., a[j]} sums to i and false otherwise.
P[sum/2][N] is what we want to calculate.
P[i,j] is true if ether P[i,j-1] is true or P[i - a[j], j-1] is true.

Here is the code:

private static boolean isGoodPartion(int[] a) {
		int N = a.length;
		int sum = 0;
		for(int i= 0; i < N; i++){
			sum += a[i];
		}
		if(sum %2 != 0){
			return false;
		}
		boolean[][] P = new boolean[sum/2+1][N+1];
		for(int i = 0; i < N+1; i++){
			P[0][i] = true;
		}
		for(int i = 1; i < sum/2+1; i++){
			P[i][0] = false;
		}
		for(int i = 1; i <= sum/2; i++){
			for(int j = 1; j <= N; j++){
				if(i < a[j-1]){
					P[i][j] = P[i][j-1];
				}else{
					P[i][j] = P[i][j-1] || P[i-a[j-1]][j-1];
				}
				
			}
		}
		return P[sum/2][N];
	}

1. Make all numbers non-negative by multiplying -1 to negative elements O(n)
2. Sort the numbers O(nlogn)
3. Find total sum
4. leftSum = 0, rightSum = TotalSum, foundMidpoint = false;
for i = 1 to length of array
{
leftSum += a[i];
rightSum -= a[i];
if(leftSum == righSum)
{
foundMidpoint = true; break;
}
}

if(!foundMidPoint)
return false;
else return true;

Step 1: - get SUM of all the elements.
Step 2: - if(SUM%2==1) printf("no")
else
find subsequence with sum = SUM/2
Step 3: - if such subsequence exist then printf("Yes");
else printf("No");

Code to generate all 2pwd N combinations. Using bit operations.

#include<stdio.h>
int main()
{
        int b[] = {1,2,3,4};
        int i,a=15;
        for(i=0;i<16;i++){
                int k=0,sum=0,j =i;
                do{

                        printf("%d",j&1);
                        sum=sum+b[k]-2*(j&1)*b[k];
                        j=j>>1;
                        k++;
                }while(k<4) ;
                printf("\n");
                printf("%d\n",sum);

        }
}

Partition problem. NP-Hard.

public static boolean find(int array []){
		int sum = 0; 
		for (int i = 0 ;i<array.length ;++i){
			sum+=array[i];
		}
		if (sum%2!=0){
			return false;
		}else{
			return find (array, sum/2,0,0);
		}
	}
	
	public static boolean find (int [] array, int sum ,int n ,int start){
		if (n==sum){
			return true;
		}else if (n>sum){
			return false;
		}else{
			for (int i = start ;i<array.length;++i){
                  n+= array[i];
                  if (find(array,sum,n,start+1)){
                	  return true;
                  }
                 n-= array[i];
                 if (find(array,sum,n,start+2)){
               	  return true;
                 }
			}
			return false;
		}

}

1) Ignoring the signs (if there are negative or positive) find the largest among them.
eg1: {-1,2,-3,5,-3}----------------> largest is 5
eg2: {-7,1,2,4}---------------------->largest is 7

2)find the sum of all remaning elemets, say is "x", then check whether
"largest - x " or largest + x" equals to zero.
eg1:x = -5---- the chk comes to zero
eg2: x = 7-----the chk comes to zero.

I think this will work and we dont have to chk for all combination.

public class SumZeroPossible {
public static void main(String[] args) {
int a[] = { -2, 2,4 };
int sum = a[0];
char sign[] = new char[a.length-1];
boolean ab = isSumZeroPossible(a, 1, sign, sum);
System.out.println(ab);
if(ab){
System.out.print(a[0]);
for (int i = 0; i < sign.length; i++) {
System.out.print(sign[i]);
System.out.print(a[i + 1]);
}
}
}

private static boolean isSumZeroPossible(int[] a, int i, char[] sign,int sum) {
if (sum == 0 && i == a.length)
return true;
else if (i == a.length)
return false;
else {
sign[i - 1] = '-';
if (isSumZeroPossible(a, i + 1, sign, sum - a[i]))
return true;
sign[i - 1] = '+';
if (isSumZeroPossible(a, i + 1, sign, sum + a[i]))
return true;
}
return false;
}

}

public static boolean canGetZeroResult(int[] arr) {
        // Bad input
        if (arr == null || arr.length == 0) {
            return false;
        }

        return canGetZeroResult(arr, 0, 0, 0);
    }

    private static boolean canGetZeroResult(int[] arr, int i, int addResult, int subtractResult) {

        // Past the end of the array: did we end up at zero?
        if (i > arr.length - 1) {
            return addResult == 0 || subtractResult == 0;
        }

        // Both add to and subtract the current element from the two results you have currently - each call makes two more calls
        return canGetZeroResult(arr, i + 1, addResult + arr[i], addResult - arr[i])
                || canGetZeroResult(arr, i + 1, subtractResult + arr[i], subtractResult - arr[i]);
    }

Worst-case runtime is exponential, 2^n since every call branches out to two more calls. I haven't really found a way you can do better, since you have to look at every element and explore how it combines with every other element. Don't believe memoization is possible.

This is the bit counter solution to generate combinations in Java

public static boolean sumsZero(int[] input) {
        long countLimit = (long)Math.pow(2, input.length - 1);
        
        for (long i = 0; i < countLimit; i++) {
            long count = i;
            int acum = input[0];
            System.out.print(acum);
            for (int j = 1 ; j < input.length ; j++) {
                if ((count & 1) == 1) {
                    acum += input[j];
                    System.out.print("+" + input[j]);
                } else {
                    acum -= input[j];
                    System.out.print("-" + input[j]);
                }
                count >>= 1;
            }
            if (acum == 0) {
                System.out.println(" Bingo");
                return true;
            }
            System.out.println();
        }
        return false;

}

1. Find the maximum number.
2. If the sum of all numbers is = 0 or twice the maximum.
I think this will give you the correct output

This is a partition problem. The basic idea is to know if there is s subset of elements that can sum up to k .. where k is the sum of all elements in the array. The trick is to know how to find the elements that can sum up to K but consider that:

For any number on the array, there are two options: 1- Take it 2- Ignore it. For each of these options, you have to try all other possibilities for other number. This lead to 2^n performance.

A Java implementation

public boolean findPartition(int [] array){
		int k = 0;
		for (int i = 0; i < array.length; i++) k += array[i];
		return isSubset(array, array.length, k);
	}
	
	public boolean isSubset(int [] array, int n, int sum){
		if(sum==0) return true;
		if(n==0 && sum!=0) return false;
		// If last element is greater than sum, then ignore it
		if(array[n-1]>sum) return isSubset(array, n-1, sum);
		//check if sum can be obtained by any of the following
	    //  (a) excluding the last element
	    //  (b) including the last element
		return isSubset(array, n-1, sum) || isSubset(array, n-1, sum-array[n-1]);
	}

The first recursive version is easier to code.
We can also use DFS (backtrack) to search the entire array.

The complexity is also O(2^n).

// Use DFS to judge whether we have get a zero...

public boolean check(int[] a) {
return DFS(a, 0, 0);
}

public boolean DFS(int[] a, int i, int sum) {
if ( i == a.length )
return sum==0;
return DFS(a,i+1, sum+a[i]) || DFS(a, i+1, sum-a[i]);
}

We can create a tree in the following way:
1. Root of the tree is element zero
2. Start from i = 0. Add A[i] as left child and -A[i] as right child to each of the existing leaf nodes

Now the problem is finding if there is a path from root to any leaf with sum 0

bool CheckForZero(node *n, int sum)
{
     if(n == NULL)
     {
          return sum == 0;
     }
     sum += n->number;
     bool reachedZero = CheckForZero(n->left, sum);
     if(reachedZero)
     {
                   return true; 
     }
     return CheckForZero(n->right, sum);
}

CheckForZero(root, 0) will check if any combination will result in zero.

public static void test(int[] array) {
// Base case

int number = (int) Math.pow(2, array.length);

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

int j = i;
int index = array.length-1;
int sum = 0;
int[] temp = array;
while (j > 0) {

if ((j & 1) == 1 && index>-1) {
temp[index] *= -1;
}
sum += temp[index];
j >>= 1;
index--;
}

if (sum == 0 && index == -1) {

for (int ptr = 0; ptr < temp.length; ptr++) {
System.out.println(temp[ptr]);
}
return;
}

}
}

We can use DP here to reduce the time complexity from O(2^n)

1. Convert the -ve integers in the array to +ve (i.e. take their absolute values)
2. Find the sum of the array
3. if sum is odd => no solution exists, return
4. else find if a subset of array elements exists that adds up to sum/2 , use DP here to find that subset (subset sum problem)

5. if yes, then the array elements can be added to yield an effective sum of 0

Here's my code:

int main()
{
    int n;
    cin>>n;
    int arr[n],sum=0;
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
        if(arr[i]<0)
            arr[i] = -arr[i];
        sum+=arr[i];
    }
    if(sum&1)
    {
        cout <<"No Possibility"<<endl;
        return 0;
    }
    sum/=2;
    bool dp[sum+1][n+1];
    int i,j;
    for(j=0;j<=n;j++)
        dp[0][j]=true;   /* result is true if sum = 0 */
    for(i=1;i<=sum;i++)
        dp[i][0]=false; /* result is false if sum>0 and elements are 0*/

    for(i=1;i<=sum;i++)
    {
        for(j=1;j<=n;j++)
        {
            dp[i][j]= dp[i][j-1]; /*exclude current element */
            if(arr[i-1]<=i)
                dp[i][j] = dp[i][j]||dp[i-arr[i-1]][j]; /*include it*/
        }
    }
    if(dp[sum][n]) /*if true*/
        cout<<"Possibility exists"<<endl;
    else
        cout <<"No Possibility"<<endl;
        
}

I told my friends about this problem. They insisted on a brute force answer. I was the first to get it down. Enjoy the worlds least efficient code. Please show a test case that doesn't work for this. Very very sloppy code here.

#include <array>
using namespace std;

bool sumsToZero(int sum[10]){
	int addup=0;
	int grid[10] = {0,0,0,0,0,0,0,0,0,0};
	
	for(int i=0;i<10;i++){
		grid[i] = 0;

		for(int j=0;j<10;j++){
			addup=0;
		
			if(i!=j && grid[j]==0){
				grid[j]=1;}
			else if(i!=j && grid[j]==1){
				grid[j]=0;}
			
				for(int x=0; x<10; x++){
					if(grid[x]==0){addup +=sum[x];}
					if(grid[x]==1){addup -=sum[x];}
				}
				if (addup == 0){return true;}
				if(i>0){
					grid[i-1] = 1;}
		
		}
	}
	return false;
}

int main(){
	int x[10]={10,5,2,3,10,4,7,3,5,15};
	std::cout<<sumsToZero(x)<<std::endl;

	system("pause");

return 0;
}

public class HelloWorld{

public static void main(String []args){
int[] arr={3,6,2};

System.out.println(f(arr));
}
public static boolean f(int[] arr)
{
return f(arr, 0, 0, 0) || f(arr, 0, 0, 1);
}
private static boolean f(int[] arr, int start, int sum, int sign)
{
if(start>arr.length)
{
return false;
}
if(start==arr.length && sum==0)
{

return true;
}
if(start==arr.length)
{

return false;
}
if(sign==0)
{
sum+=arr[start];
}
else
{
sum-=arr[start];
}

boolean cond1= f(arr, start+1, sum, 0);
boolean cond2= f(arr, start+1, sum, 1);
return cond1 || cond2;
}
}

public class HelloWorld{

public static void main(String []args){
int[] arr={3,6,2};

System.out.println(f(arr));
}
public static boolean f(int[] arr)
{
return f(arr, 0, 0, 0) || f(arr, 0, 0, 1);
}
private static boolean f(int[] arr, int start, int sum, int sign)
{
if(start>arr.length)
{
return false;
}
if(start==arr.length && sum==0)
{

return true;
}
if(start==arr.length)
{

return false;
}
if(sign==0)
{
sum+=arr[start];
}
else
{
sum-=arr[start];
}

boolean cond1= f(arr, start+1, sum, 0);
boolean cond2= f(arr, start+1, sum, 1);
return cond1 || cond2;
}
}

public class HelloWorld{

public static void main(String []args){
int[] arr={3,6,2};

System.out.println(f(arr));
}
public static boolean f(int[] arr)
{
return f(arr, 0, 0, 0) || f(arr, 0, 0, 1);
}
private static boolean f(int[] arr, int start, int sum, int sign)
{
if(start>arr.length)
{
return false;
}
if(start==arr.length && sum==0)
{

return true;
}
if(start==arr.length)
{

return false;
}
if(sign==0)
{
sum+=arr[start];
}
else
{
sum-=arr[start];
}

return f(arr, start+1, sum, 0) || f(arr, start+1, sum, 1);
}
}

Step 1: convert the array into absulte values (O(n))
Step 2: sort descently (O(nLog n))
Step 3: Loop over values from biggest to lowest applying (O(n)):
- If total sum is bigger than 0, substract the value from it.
- If total sum is zero or smaller, add the value to it.

At the end, if numbers can be combined to sum zero, sum will be zero.
Total time: O(n)

Here's the Python code:

import sys

numlist = [abs(int(x)) for x in sys.argv[1:]]
numlist.sort(key=int, reverse=True)
print numlist

check = ''
summ = 0
for x in numlist:
    if summ > 0:
        summ -= x
        check += ' - ' + str(x)
    else:
        summ += x
        check += ' + ' + str(x)

if summ == 0:
    print 'Yes!'
else:
    print 'No!'
    
print check + ' = ' + str(summ)