#include <stdio.h>

#include <string.h>

#define MIN2(a, b) ((a) < (b) ? (a) : (b))

#define MIN4(a, b, c, d) MIN2(MIN2(a, b), MIN2(c, d))

/*Int comparator for sorting*/

int compareInt(const int *a, const int *b)

{

return *a - *b;

}

/*

This function divides the given array into two parts such that difference of their sum is minimum

Algo:

1. sort the array

2. Starting from the end, put last element into one part and last two into another part

3. From k = n-2 to 0, compare diffs of

a. smaller part + a[k] and bigger part

b. smaller part + last num of bigger part and bigger part - last num of bigger part + a[k]

c. smaller part - last num of smaller part + last num of bigger part and bigger part - last num of bigger part + a[k] + last num of smaller part

d. smaller part - last num of smaller part + last num of bigger part + a[k] and bigger part - last num of bigger part + last num of smaller part

4. if a is small, add k to smaller part

else if b is small add last number of bigger part to smaller part and a[k] to bigger part

else swap last parts and

if c is small add a[k] to bigger

else add a[k] to smaller

*/

void divide(int a[], int n)

{

int i;

/*print the given array*/

printf("\n\nGiven array: ");

for(i = 0; i <n; ++i)

printf("%d ", a[i]);

printf("\n\n");

/*sort the array*/

qsort(a, n, sizeof(int), compareInt);

/*struct to hold info about each part*/

typedef struct

{

int arr[n];

int index;

int sum;

}Part;

/*Initialize two parts*/

Part b, c;

memset(&b, 0, sizeof(b));

memset(&c, 0, sizeof(c));

b.arr[0] = a[n-1];

c.arr[0] = a[n-2];

b.index = 0;

c.index = 0;

b.sum = a[n-1];

c.sum = a[n-2];

int k = n-3;

int diff1, diff2, diff3, diff4;

int lastOfSmaller, lastOfBigger, mn;

//pointers to smaller and bigger parts

Part *smaller, *bigger;

while(k >= 0)

{

//decide smaller and biggers parts

if(b.sum < c.sum)

{

smaller = &b;

bigger = &c;

}

else

{

smaller = &c;

bigger = &b;

}

//now decide where to put a[k] in smaller or bigger part

lastOfBigger = bigger->arr[bigger->index]; //last element of bigger

lastOfSmaller = smaller->arr[smaller->index]; //last element of smaller

diff1 = abs((smaller->sum + a[k]) - bigger->sum);

diff2 = abs((smaller->sum + lastOfBigger) - (bigger->sum - a[k] - lastOfBigger));

diff3 = abs((smaller->sum - lastOfSmaller + lastOfBigger) - (bigger->sum - lastOfBigger + lastOfSmaller + a[k]));

diff4 = abs((smaller->sum - lastOfSmaller + lastOfBigger + a[k]) - (bigger->sum - lastOfBigger + lastOfSmaller));

mn = MIN4(diff1, diff2, diff3, diff4);

if(mn == diff1)

{

smaller->arr[++smaller->index] = a[k];

smaller->sum += a[k];

}

else if(mn == diff2)

{

smaller->sum += lastOfBigger;

smaller->arr[++smaller->index] = lastOfBigger;

bigger->sum += a[k] - lastOfBigger;

bigger->arr[bigger->index] = a[k];

} else{

smaller->sum -= lastOfSmaller + lastOfBigger;

smaller->arr[smaller->index] = lastOfBigger;

bigger->sum -= lastOfBigger + lastOfSmaller;

bigger->arr[bigger->index] = lastOfSmaller;

if (mn == diff3) {

bigger->sum += a[k];

bigger->arr[++bigger->index] = a[k];

} else {

smaller->sum += a[k];

smaller->arr[++smaller->index] = a[k];

}

}

k--;

}

/*print the first part*/

int p = 0;

printf("Part1: ");

while(p <= b.index)

printf("%d ", b.arr[p++]);

printf("\n\n");

/*print the second part*/

p = 0;

printf("Part2: ");

while(p <= c.index)

printf("%d ", c.arr[p++]);

printf("\n\n");

printf("Sum Diff: %d\n\n", mn);

}

int main()

{

int a[] = {14, 9, 7, 6, 5, 3};

divide(a, sizeof(a)/ sizeof(int));

}

Advertisements

Awesome answer…I appreciate the effort you take to write n build such a nice and efficient code..The logic of program has no bugs butSome suggestions to make it flawless,1)int compareInt(const int *a, const int *b){ return *a – *b;}should beint compareInt (const void * a, const void * b){ return ( *(int*)a – *(int*)b );}2) Missing #include directive algorithm.h to make qsort visible for compiler.3)You just cannot declare array with a variable size, so arr[(n+1)/2], in definition of Part struct,is incorrect..

Can you please elaborate more on the partel = *(bigger->index); //last element of biggerdiff1 = smaller->sum + a[k] – bigger->sum;diff2 = smaller->sum +(el << 1)-bigger->sum-a[k];i cant get logic behind it..and why are you doing "e1 << 1" ??

it is standard knapsack problem solvable in O(n^2) using dynamic solution

14 9 7 6 5 3

if the problem is "split the array into two set such that – how to implement it?the no. of elements of each set is equal or differ by 1 and also the sum diff. also min.

i cant get logic behind it..and why are you doing "e1 << 1" ??

Can Any One please explain the logic behind the (el << 1) .. EAGERLY WAITING ….

diff2 = sum(smaller set + last element of bigger) – sum(bigger set + a[k] – last element of bigger) = smaller->sum + el – bigger->sum +el – a[k] = smaller->sum + 2*el – bigger->sum – a[k]2*el can also be written as el << 1.