CareerCup

Knapsack based DP solution can solve it in O(nW) time, where W = sum_of_elements/2

1. Divide the array into two sets
2. sort the sets.
3. compute sum and find the closest number to the difference using binary search (lower bound) and move it to the other set.
4. Repeat until the difference remains constant
5. should converge really quick

as ftfish pointed out flaws in gekko's algorithm, I've modified the algorithm it a little bit. This is bounded by a quadratic complexity:

///a. Split array into two arrays array1 and array2. Sort them.
	     //Now the general idea of the algorithm is to move elements from heavier array to lighter array,
	      //if direct move is not possible, then swap. Also assume sum(array1)>sum(array2) and we always
	      // move/swap smaller or equal elements from array1 to array2

	///LOOP 1. Move as many elements as possible from array1 to array2 minimizing the difference
		find lowerbound of 'diff/2' in array1 in array1 and move to array2,
		  break loop when (diff/2 < min(array1) & diff > 0.0)

	///LOOP 2. Swap as many elements as possible between array1 & array2 minimizing the difference
		For every element 'x' in array2 we find (lowerbound of x+(diff/2)) in array1 and 
		swap with the 'x' in array2 which minimizes difference the most.

	Complexity: // for simplicity sake even though we split 'n' elements into two arrays for complexity analysis I just use 'n' rather than 'n/2'
	a : O(n)
	Loop 1: O(n) because we always find the lower bound in array1 and at some point either diff==0 or ((diff/2) < min(array1) & diff>0). 
		The second condition is bound by 'n' iterations or array1.size()
	Loop 2: O(n*(n*log(n))): because for every element in array2 we do a lowerbound search in array1 --> n*logn 
                                 and since we always try to find lower bound in array1 the loop should terminate in array1.size()--> n*n*logn 

	Total Complexity: O(n + n + n*(n*log(n))) --> O((n^2)*log(n)))

How do u prove this always works ??

It does not say the two sets have equal size. Did you consider this? How did you divide the array into two sets in the first place? Did they have equal size?

1) Sort all the numbers present in an array.
2) Take the Odd numbered elements into one array and even numbered elements into another array
3) Now calculate the sums of those two sets.
4) Calculate the difference between sum1,sum2.

I think that this difference should be minimal.

I think the problem is NP-complete, the solution given a above is a good approximate algorithm, but won't always find the optimal.

Take out the minimun from the array and put all the remaining elements on the other side.

so minimun number - (sum of remaning ) will give me the minimun :)

1.Sort all number first.
2.take first element in one array and second element in another array.
3.Decide? In which array we need to put next element,check the sum of the arrays and put the element on that array which have minimum sum.
4.repeat above 3 process at end of number.

example:{8,10,4,3,4,1}

1.Sort:{10,8,4,4,3,1}
2. array 1:{10}
array 2:{8}

3. Now we have to make decision in which array we have to put next number,So obvious
{10},{8,4}
and next iteration
{10,4},{8,4} //because first array have minimum sum
and next
{10,4},{8,4,3}
and next
{10,4,1}{8,4,3}

Well the solution would vary depending on whether we need to split the array into two equal halves or into two parts with varied number of elements

This is the worst complexity but the perfect result -

for(i=0;i<MAX;i++)
                printf("  %d  ",arr[i]);

        for(i=0;i<MAX;i++)
                total += arr[i];

        first = total/2;
        second = total - first;

        for(i=0;i<MAX/2;i++)
        {
                first_sum += arr[i];
                secnd_sum += arr[MAX/2+i];
        }
        for(i=0;i<MAX/2;i++)
        {
                for(j=MAX/2;j<MAX;j++)
                {
                        temp = secnd_sum - arr[j] + arr[i];
                        if(temp == first || temp == second)
                        {
                                temp = arr[i];
                                arr[i] = arr[j];
                                arr[j] = temp;
                                temp = 0;
                                break;
                        }
                }
                if(temp == 0)
                        break;
        }

O(N*Value) to get available subset sum to value ,first Value init To Sum/2,then modify value to neighbor value ,worst case O(N*M*M)

#include<stdio.h>
#include<math.h>
int size=11;
int arr1[size]={0};
int Final[size];
int MinDiff=100;
void FindSubset(int Input[],int Index,int RequiredSum,int Tmpsum)
{
if(Index>=size)
{
int x=0;
x=abs(Tmpsum-RequiredSum);
if(MinDiff>x)
{
int i=0;
for(;i<size;i++)
{
Final[i]=arr1[i];
}
MinDiff=x;
}
return;
}
arr1[Index]=Input[Index];
FindSubset(Input,Index+1,RequiredSum,Tmpsum+Input[Index]);
arr1[Index]=0;
FindSubset(Input,Index+1,RequiredSum,Tmpsum);
}


int main()
{
int Input[size];
int i=0,TotalSum=0,RequiredSum=0;

for(;i<size;i++)
{
printf("enter %dth element:\n",i);
scanf("%d",&Input[i]);
TotalSum+=Input[i];
}
RequiredSum=TotalSum/2;

FindSubset(Input,0,RequiredSum,0);
for(i=0;i<size;i++)
{
if(Final[i]!=0)
printf("%d\t",Final[i]);
}

i just assume the input size is 11 if u are intresstedthe please change the size....and it is working fine in gcc ..please if u find anything wrong then let me know...i use the concept of Backtracking........initially i find the sum of all the array then i half the sum.....scince i am not sure thatthe given array will be partationed in two subset whose difference is 0 so i am concentrating on the minimum diffrence .......

Greedy Algorithm Should Work.

Algo:
Input: Array ( input[] ) of Size N(0,N-1)
Out put: Two arrays so that absolute error is minimum

1. Initialize two arrays arr1[], arr2[] each of size N-1(0,N-2)
2. Sort the input[]
3. for i= 0: N-1
if(either arr1[] or arr2[] is empty add to it)
4. if( sum(arr1[])+sum(arr2[]) < input[I] )
arr1[] = arr1[]+arr2[] arr2[] = input[I]
else
find the nearest elments to input[i]/2 in either arr1[] or arr2[] ( but not always)
add the element from arr1[] to arr2[] or viceversa
add input[I] to array where we moved the element.


Example:
1 4 10 40 50

arr1[] = {} arr2[] = {}
I = 0, input[I] = 1
arr1[] is empty. So add to it.
arr1[] = {1} arr2[] = {}
I = 1 input[I] = 4
arr1[] is not empty. arr2[] is empty
add to arr2[].
arr1[] = {1} arr2[] = {4}
I = 2 input[I] = 10
arr1[] and arr2 are not empty.
10 > sum(arr1[])+sum(arr2[])
so move arr2[] to arr1
arr1[]={1,4} arr2[] = {10}
I = 3 input[I] = 40
40 > sum(arr1[])+sum(arr2[])
so move arr2[] to arr1
arr1[]={1,4, 10} arr2[] = {40}
I = 4 input[I] = 50
40 < sum(arr1[])+sum(arr2[])
50/2 = 25. shortest elements distance is 15 (1 4 10)
arr2[]]= { 50} arr2[] = {40,1,4,10}

for one last time (50-55)/2 = {1}
arr1[] = { 40,10,4) arr[2] = {1,50)