CareerCup

Its balanced partition problem : people.csail.mit.edu/bdean/6.046/dp/dp_4.swf

This question resembles "Find the subset sum problem" where sum = total_sum/2. Find the subset whose sum is as close as possible to the half of the total_sum. And produce the answer.

Here is my thinking, not sure if it is optimized. Let define I is the input array, also assume element in I all positive, the X is the part of array with + sign, Y is the part of array with - sign, so sum(X)-sum(Y) is the value we wanted, we have:
sum(X)+sum(Y)=sum(I)
sum(X)-sum(Y)=sum(I)-2*sum(Y)=2*(0.5*sum(I)-sum(Y)). So the question turns into another form: we need to find the Y, which is part of I, its sum is mostly close to value constant 0.5*sum(I) for specified input.
For this question i am thinking of algorithm as bellow:
1> sort I
2> build an array sumInput[x], which is the sum of element in I from index 0 to x.
3> Define a function find_closest(I, index, *pCurrentMin, target)
III> if(index<0) return
a> if(target-sumInput[index]> *pCurrentMin), you can not get closer, return
b> if(I[0]-target> 0), return, you can not get closer.
c> if(I[index]==target) *pCurrentMin=0; return;
d> if(I[index]<target) if(*pCurrentMin> target-I[index]) *pCurrentMin=target-I[index],
e call find_closest(I, index-1, pCurrentMin, target-I[index]); if *pCurrentMin==0, return
f> call find_closest(I, index-1, pCurrentMin, target)

4> call find_closest(I, n-1, ¤tMin, 0.5sumInput(n-1)),
currentMin is initialized to 0.5sumInput(n-1);

The question require DP
here is the algorithm
Let me first draw the matrix here for above example

2 1 0 0 0
   1 2 0 0
      3 1 1
         4 2
            2

and output is upper rightmost point whose index is i=0;j = n;
Here is algo

same matrix multiplication DP program with one difference which is here you have to apply abs(sub(M[i][k],M[k][j])) instead of addition and multiplication.
      min function is again here,

complexity : O(n*n) + O(n*n)
if we also want to know the sign of each number in the case of minimum sum, then we require one more matrix of size n*n.

Agree with sum/2 approach....

Find sum of all elements
Try to get set of element which makes total sum/2

#include<stdio.h>
 #include <iostream>
 #include <math.h>
 
 int main()
{ 
	int arr[]={1,2,3,4,3,2,1,4};
	int hash[100000]= {0};
	printf(" inputs are :" );
	for(int i=0;i<sizeof(arr)/sizeof(int);i++)// to show all input
	{
           printf(" %d ", arr[i]);
    }
	
	for(int i=0;i<sizeof(arr)/sizeof(int);i++)
	{
	       hash[arr[i]]= hash[arr[i]] + 1;
	        if(hash[arr[i]] %2 ==1)
                hash[arr[i]] = 1;
	}

    int sum =0;
	int j = 0;
	for(int i=0;i<sizeof(hash)/sizeof(int);i++)
	{
            if(hash[i] == 1)
            {
               sum = sum + i;
               j++;
            }             
	}
	
	int temp[j];
	int k=0;
	for(int i=0;i<sizeof(hash)/sizeof(int);i++)
	{
	     if(hash[i]==1)
         {
            temp[k] = i;
            k++;
         }
	}

	int maxSum = sum, minSum = 0;
	int dif=sum;
	for(int i=0;i<sizeof(temp)/sizeof(int)-1;i++)
	{
         minSum = minSum+temp[i];
         maxSum = maxSum -temp[i];
         
         
         if(dif > abs(maxSum -minSum) )
         {
                dif = abs(maxSum -minSum);
         }
         
	}
	printf("\nresult: %d\n", dif);
	getchar();
	return 0;
}

#include<stdio.h>
 #include <iostream>
 #include <math.h>
 
 int main()
{ 
	int arr[]={1,2,3,4,3,2,1,4};
	int hash[100000]= {0};
	printf(" inputs are :" );
	for(int i=0;i<sizeof(arr)/sizeof(int);i++)// to show all input
	{
           printf(" %d ", arr[i]);
    }
	
	for(int i=0;i<sizeof(arr)/sizeof(int);i++)
	{
	       hash[arr[i]]= hash[arr[i]] + 1;
	        if(hash[arr[i]] %2 ==1)
                hash[arr[i]] = 1;
	}

    int sum =0;
	int j = 0;
	for(int i=0;i<sizeof(hash)/sizeof(int);i++)
	{
            if(hash[i] == 1)
            {
               sum = sum + i;
               j++;
            }             
	}
	
	int temp[j];
	int k=0;
	for(int i=0;i<sizeof(hash)/sizeof(int);i++)
	{
	     if(hash[i]==1)
         {
            temp[k] = i;
            k++;
         }
	}

	int maxSum = sum, minSum = 0;
	int dif=sum;
	for(int i=0;i<sizeof(temp)/sizeof(int)-1;i++)
	{
         minSum = minSum+temp[i];
         maxSum = maxSum -temp[i];
         
         
         if(dif > abs(maxSum -minSum) )
         {
                dif = abs(maxSum -minSum);
         }
         
	}
	printf("\nresult: %d\n", dif);
	getchar();
	return 0;
}

Greedy Dual Knapsack.
Sort in Decreasing order and then just divide the array into 2 knapsacks such that their difference is min.

import java.io.*;
import java.util.*;

public class DualKnapsack {
public static void main(String[] args) {
ArrayList<Integer> array = new ArrayList<Integer>();

for(int i=0;i<10;i++){
array.add((int) (Math.random()*100));
}
Collections.sort(array,Collections.reverseOrder());

System.out.println(array);
System.out.println(sum(array));
int neg=0;
int pos=0;

for(int i=0;i<array.size();i++){
if(pos>neg){
neg+=array.get(i);
array.set(i,array.get(i)*(-1));
}else if(neg>pos){
pos+=array.get(i);
}else{
pos+=array.get(i);
}
}
System.out.println(array);
System.out.println(sum(array));
}

private static int sum(ArrayList<Integer> array) {
int sum=0;
for(int e:array){
sum+=e;
}
return sum;
}
}

Just use two knapsacks and then greedily approach the problem such that the difference between the knapsacks is min.

{
import java.io.*;
import java.util.*;

public class DualKnapsack {
public static void main(String[] args) {
ArrayList<Integer> array = new ArrayList<Integer>();

for(int i=0;i<10;i++){
array.add((int) (Math.random()*100));
}
Collections.sort(array,Collections.reverseOrder());

System.out.println(array);
System.out.println(sum(array));
int neg=0;
int pos=0;

for(int i=0;i<array.size();i++){
if(pos>neg){
neg+=array.get(i);
array.set(i,array.get(i)*(-1));
}else if(neg>pos){
pos+=array.get(i);
}else{
pos+=array.get(i);
}
}
System.out.println(array);
System.out.println(sum(array));
}

private static int sum(ArrayList<Integer> array) {
int sum=0;
for(int e:array){
sum+=e;
}
return sum;
}
}
}

package interview.permute;

public class Sum 
{
	public void findMinimumSum(int[] A)
	{
		int minimumSum = Integer.MAX_VALUE;
		int currentDifferene = minimumSum;
		int i = 0;
		int j = A.length -1;
		
		while (i != j && currentDifferene != 0)
		{
			if (currentDifferene == Integer.MAX_VALUE)
				currentDifferene = A[j] - A[i];
			else
			{
				currentDifferene -= A[i];
			}
			
			if (currentDifferene < 0)
			{
				j--;
				
				if (j == i)
					break;
			}
			
			if (currentDifferene == 0)
				break;
			
			i++;
		}

		for (int count = 0 ; count < A.length ; count++)
		{
			if (count <= i)
				System.out.print(" " + "-" + A[count]);
			else
				System.out.println(" " + A[count]);
		}
	}
	
	public static void main(String[] args) 
	{
		int[] A = new int[]{1, 3, 4};
		
		Sum s = new Sum();
		
		s.findMinimumSum(A);
	}
}

this seems to be working
What I am trying to do is:

1. Sort the array
2. Remove any duplicate (at the end, you will have to add then in pairs, for e.g. 2, -2 etc)
[I have skipped above two steps in my code, to make the logic simpler]

3. Traverse from start and end, keep minimizing the sum, until you reach zero, or you end up on the same element..

Please comment back, if you find any bug

A greedy way would be to first sort the array, iterate through it starting with the largest item and always assign the next element to the set (the plus or minus set) that is currently smaller. It would run O(N). Based on intuition I think it's pretty much optimal, because the best option as far as I can figure to balance it is always to assign the next-largest to make up as much of the difference as possible.

public static int [] greedy(int [] arr)
	{
		Arrays.sort(arr);
		
		Vector <Integer> aItems = new Vector();
		Vector <Integer> bItems = new Vector();
		int aSum = 0;
		int bSum = 0;
		for(int i = arr.length-1; i >= 0; i--)
		{
			if(aSum <= bSum)
			{
				aSum += arr[i];
				aItems.add(arr[i]);
			}
			else
			{
				bSum += arr[i];
				bItems.add(arr[i]);				
			}
		}
		
		for(Integer i : aItems)
		{
			System.out.print(i + " + ");
		}
		System.out.println(" = " + aSum);
		for(Integer i : bItems)
		{
			System.out.print(i + " + ");
		}
		System.out.println(" = " + bSum);

		int [] rarr = new int[arr.length];
		int at = 0;
		if(aSum > bSum)
		{
			for(int i : aItems)
				rarr[at++] = i;
			for(int i : bItems)
				rarr[at++] = -i;			
		}
		else
		{
			for(int i : bItems)
				rarr[at++] = i;
			for(int i : aItems)
				rarr[at++] = -i;						
		}
				
		return rarr;
	}

www[dot]geeksforgeeks[dot]org/tug-of-war/

My thinking keep the sum close to 0 as possible.
1.) Sort it. O(nlogn)
2.) Anything with a duplicate pair you negate one and keep the other. O(n)
3.) Subtract the largest number and the next largest number to get a new current sum total.
4.) while current sum total greater than or equal zero. Subtract the largest number possible to keep the total at or above 0.
This can be done in O(logn) using a modified binary search that returns the predecessor of the value you looking for if its not found.
5.) Once you can't subtract anymore numbers. Go back to step 2.

Logic seems right?