CareerCup

This is example of famous balanced partitioning problem. You need to basically find if any subset of set S sums up to N=(a1+a2+a3+...an)/2. If yes then other set will automatically have sum (a1+..+an)/2. However if that is not true then we will try if a subset has sum N-1, N-2,N-3 etc. Now the question is how to find if a subset of S sums up to some number. For this we use dynamic programming.
P(i,j) is true if there is a subset from among first i elements that sum up to j. The recurrence relation will be
P(i,j) = 1 if P(i-1,j) = 1 // there is a subset of (i-1) elements that sum up to j
OR if P(i-1, j-a(i) ) = 1 // include the ith element in the subset

How about the following logic:
1. Sort the set in decreasing order.
2. Repeat the following until set is empty:
a) Put 1st/next element in first set
b) Traverse and keep putting the next elements in the second list until sum of second exceeds sum of first.
c) Go to a) if list is not empty

hii i m not sure for this solution but please have a look:
1)lets put all the elements in a array nad sort them
2)then map 1st element and last element to first set and 2ns and second last to secondset and 3rd and 3rd last to first like this.......

may be we will end up in minimum difference....

#include<conio.h>
#include<stdio.h>
int diff(int a,int b) // finding |a-b|
{
if(a>b)
return a-b;
else
return b-a;
}


int main()
{
int arr[100]; // input array
int n; // no. of elements
printf("enter no. of element in array");
scanf("%d",&n);
for(int i=0;i<n;i++)
{
printf("enter element..");
scanf("%d",&arr[i]);
printf("\n");
}
int s1[100]; //subset s1
int s2[100]; //subsets2
for(int i=0;i<n;i++)
{
s1[i]=0; // all elements of s1 to be 0
s2[i]=0; // ''
}
int sum1,sum2,difference1,difference2;
s1[0]=arr[0];
sum1=s1[0]; // current sum of s1 array elements
s2[0]=arr[1]; // current sum of s2 array elements
sum2=s2[0];
int a,b;
a=1; // free index of s1
b=1; // free index of s2
for(int i=2;i<n;i++)
{
difference1=diff((sum1+arr[i]),sum2); // adding new element to s1 and finding difference b/t s1 & s2
difference2=diff(sum1,(sum2+arr[i])); //adding new element to s2 and finding difference b/t s1 & s2
if(difference1 < difference2)
{
s1[a]=arr[i];
sum1+=arr[i];
a++;
}
else
{
s2[b]=arr[i];
sum2+=arr[i];
b++;
}
}

printf("....s1 set....\n");
for(int i=0; i<n;i++)
{
printf("%d,",s1[i]);
}
printf("\n......s2 set...\n");
for(int i=0; i<n;i++)
{
printf("%d,",s2[i]);
}

printf("\n diffrence is=%d",diff(sum1,sum2));



getch();
return 0;
}

This is a dynamic programming question. Here's the approach I would take:

S={12,4,7,1,6,3,3}

1) Single element is itself

2) Two elements is two sets of each

3) Three elements

(12,4,7) => (12,{4,7}) or ({12,4},7) or ({12,4,7})
=> (12,11) or (16,7) or (23)
=> (12,{4,7})

And so on until the table is built up.

package yahoo;

import java.util.ArrayList;

public class Divide_Two_Set_Min_Difference {
public static ArrayList<Integer> get_results(int[] test){
ArrayList<Integer> results=new ArrayList<Integer>();
int sum=computer_sum(test);
System.out.println("sum: "+sum);
for(int i=sum/2;i!=sum+1;i++){
if(whether_sum(test,0,test.length-1,i,results)){
System.out.println("haha: "+i);
return results;
}
}
return null;
}
public static boolean whether_sum(int[] test,int begin,int end,
int aim,ArrayList<Integer> results){

if(aim<0){
return false;
}
if(begin>end){
return false;
}
if(test[begin]==aim){
results.add(test[begin]);
return true;
}
if(whether_sum(test,begin+1,end,aim-test[begin],results)){
results.add(test[begin]);
return true;
}
if(whether_sum(test,begin+1,end,aim,results)){
return true;
}
return false;
}
public static int computer_sum(int[] test){
int sum=0;
for(int i=0;i!=test.length;i++){
sum+=test[i];
}
return sum;
}
public static void show(ArrayList<Integer> results){
for(int i=0;i!=results.size();i++){
System.out.println(results.get(i));
}
}
public static void main(String[] args) {
int[] test=new int[]{12,4,7,1,6,3,3};
ArrayList<Integer> results=get_results(test);
show(results);

}
}

Here's the pseudo-algorithm described in terms of dynamic programming:

Subset(empty) = 0
SubSet(i,i) = Subset(i)
Subset(i,i+1)=Subset(i,i) + SubSet(i+1,i+1)
Subset(i,i+n)= For a=i to i+n do 
		Max(Subset(i,a-1),Subset(a,i+n))

Overall, it's a form of tail-recursion.

- Create S1=S and S2 empty. Sum1 is the sum of S and sum2 is the sum of S2 (0 to start)
- Keep iterating over S1
- Find an element in S1 which if moved to S2 would minimize (sum1-sum2). If you do find it, then move the element from S1 to S2 and update sum1 and sum2. If you can't find such an element, then break the loop.

I was able to get the following output

Input=[12, 4, 7, 1, 6, 3, 3]
S1=[4, 7, 1, 3, 3]
Input=[3, 3, 12, 4, 7, 1, 6]
[3, 3, 4, 7, 1]
Input=[3, 3, 2, 2, 2]
[2, 2, 2]
Input=[5, 3, 2, 13, 2]
[5, 3, 2, 2]
Input=[5, 5, 4, 3, 3]
[4, 3, 3]

Why can't we follow this approach, and I know sorting has been discussed before but please bear with me:

1. Sort the array
2. Keep two variable, left_sum, right_sum
3. Keep two variable more variable, low, high

low = 0;
high = arr.length - 1;
while (low < high) {
   if (low_sum > right_sum) {
      high--;
      right_sum = arr[high];
   }
   else if (low_sum < right_sum) {
      low--;
      left_sum = arr[low];
   }
   else {
      if(low>=high) break;
      high--;
      right_sum = arr[high];
      low--;
      left_sum = arr[low];
   }
}

Should this not give a minimised partition? I also checked with the dynamic programming question, it looks better than O(n^2 k) solution, also, we do not need to have the numbers in the range of [0,k] - which means we can do it for negative numbers too.
Please let me know your thoughts

def balancePoint(li):
	left = li[0]
	right = 0
	minPoint = 0
	location = 0
	for i in li:
		right = right + i 
	minPoint = left - right	
	if minPoint <0:
		minPoint = -minPoint

	for i in range(0,len(li)-1):
		if left == right:
			print "Least value "+str(i)
			return
		else:
			temp = left-right
			if temp < 0:
				temp = -temp
			if temp < minPoint:
				minPoint = left-right
				if minPoint < 0 :
					minPoint = -minPoint
				location = i
		left = left + li[i+1]
		right = right - li[i]
	print str(minPoint)+" at "+str(location)


if __name__ == '__main__':
	li = [1,2,3,4,6,11]
	balancePoint(li)

/// Using DP
/// m[i+1][j] = 1 /// IF m[i][j-A[i+1]] = 1
/// m[i+1][j] = 0; /// IF m[i][j-A[i+1]] = 1
/// Time Complexity O(N * S) Space Complexity O(S)

int run()
{
///int A[] = {12, 4, 7, 1, 6, 3, 3};
///int A[] = {12, 100};
int A[] = {3, 3, 2, 2, 2};

int s = 0;
for(int i = 0; i < sizeof(A) / sizeof(A[0]); i ++) {
s += A[i];
}
print_v(A, sizeof(A) / sizeof(A[0]));
int m[s/2 + 1];
memset(m, 0, sizeof(m));
for(int i = 0; i < sizeof(A) / sizeof(A[0]); i ++) {
for(int k = s/2; k >= 0; k --) {
if(m[k] && (k + A[i] < s/2 + 1)) m[k + A[i]] = 1;
}
m[A[i]] = 1;
///print_v(m, s/2 + 1);
}
int i = 0;
for(i = s/2; i >= 0; i --) {
if(m[i]) break;
}
printf("s : %d i : %d\n", s, i);
return 0;
}

int find_balance_point(int *input, int n)
{
	int left_sum, right_sum;
	int sum = 0;
	if (input == NULL)
		return -1;

	for (int i = 0; i < n; i++)
		sum += input[i];

	left_sum = input[0];
	right_sum = sum - input[0];
	for (int i = 1; i < n; i++) {
		left_sum += input[i];
		if (left_sum == right_sum)
			return i;
		right_sum -= input[i];
		if (left_sum == right_sum)
			return i;
	}
	return -1;
}