# Divide the array in two subarray such that difference of the sum is minimum?

2,822 views

Divide the array in two subarrays of n/2 sizes each such that the difference of the sum of two subsets is as minimum as possible. If n is even, then sizes of two subarray must be n/2 and if n is odd, then size of one subarray must be (n-1)/2 and size of other subset must be (n+1)/2.

posted Nov 12, 2013

prakash, can you share example ? am not able catch this.

``````void display(int list[], int n)
{
int i;
for(i = 0 ; i < n; ++ i)
{
printf("  %d", list[i]);
}
printf("\n");
}

int find_diff(int num1, int num2)
{
if(num1 > num2)
return num1 - num2;
else
return num2 - num1;
}

void balance(int sum2, int sum1, int a2[], int a1[], int n)
{
int diff = (sum2 - sum1)/2;
int min, bal = 999999;
int idx1 , idx2, temp1, temp2;
int i = 0; int j = 0;
int FLAG = FALSE;
while(i < n && j < n)
{
min = a2[j] - a1[i];
if (min > 0)
{
if (min < diff * 2)
{
min = find_diff (min, diff);
if (bal > min)
{
bal = min;
idx1 = i;
idx2 = j;
i++;
FLAG = TRUE;
}
else
j++;
}
else
j++;
}
else
i++;
}
if (FLAG)
{
temp1 = a1[idx1];
temp2 = a2[idx2];
for (i = idx1; i >= 0; i--)
{
if(temp2 > a1[i - 1])
a1[i] = a1[i - 1];
else
{
a1[i] = temp2;
break;
}

}
for (i = idx2; i < n; i++)
{
if(temp1 < a2[i + 1])
a2[i] = a2[i + 1];
else
{
a2[i] = temp1;
break;
}
}

sum1 = sum1 - temp1 + temp2;
sum2 = sum2 - temp2 + temp1;

if (sum2 > sum1)
balance(sum2, sum1, a2, a1, n);
else
balance(sum1, sum2, a1, a2, n);
}
else
{
printf("\n\n SUM = %d\t",sum1);
display(a1, n);
printf("\n\n SUM = %d\t",sum2);
display(a2, n);
}
}

void divided_array(int a[], int n)
{
int a1[n/2], a2[n/2];
int sum1 = 0;
int sum2 = 0;
int k = 0;
int i;

sort_array(a,n);

a1[0] = a[n-1];
a2[0] = a[n-2];

for (i = n-2; i >= 2; i-=2)
{
sum1 += a1[k];
sum2 += a2[k];
k += 1;
if (sum1 > sum2)
{
a1[k] = a[i - 2];
a2[k] = a[i - 1];
}
else
{
a1[k] = a[i - 1];
a2[k] = a[i - 2];
}
}

sum1 += a1[k];
sum2 += a2[k];

if (sum2 > sum1)
balance(sum2, sum1, a2, a1, k+1);
else
balance(sum1, sum2, a1, a2, k+1);
}
``````

I did not implement the function sort_array.
Better to use heap sort.

`````` 95 135 68 11 84 26 66 139 118 116 65 18

SUM = 469        135  118  95  84  26  11

SUM = 472        139  116  68  66  65  18
=========================================================
95 145 77 34 169 79 35 67 149 33 166 77

SUM = 561        169  149  95  79  35  34

SUM = 565        166  145  77  77  67  33
=========================================================
95 21 80 131 6 58 18 139 159 89 81 11

SUM = 441        139  131  81  58  21  11

SUM = 447        159  95  89  80  18  6
=========================================================
67 21 80 131 82 58 18 58 159 89 81 11

SUM = 427        159  89  82  58  21  18

SUM = 428        131  81  80  67  58  11
``````
Thanks in advanced If some one can reduce the complexity.

first find out the total of all the given numbers.. lets say it's total_sum.. then create two new arrays.. lets say A1 and A2 .. start putting elements in the first array A1 until sum of all the elements of A1>total_sum/2; then put rest numbers into A2.. then A1 and A2 will be the two subsets of minimum difference

answer Dec 3, 2013 by anonymous
:) Good idea
Please code it and tell complexity :)
package poc.random;

import java.util.Arrays;

public class Example {

public static void main(String[] args) {

//    int arr[] = {10,5,12,6,3,8};
//    int arr[] = {21,2,12,3,5,9};
int arr[]= {95, 135, 68, 11, 84, 26, 66, 139, 118, 116, 65, 18};
//    int arr[]= {67, 21, 80, 131, 82, 58, 18, 58, 159, 89, 81, 11};
//    int arr[]= {5, 21, 80, 131, 6, 58, 18, 139, 159, 89, 81, 11};
//    int arr[]= {95, 145, 77, 34, 169, 79, 35, 67, 149, 33, 166, 77};
int subArr1[]= new int[arr.length/2];
int subArr2[]= new int[arr.length/2];
subArr1[0] = arr[0];
subArr2[0] = arr[1];
subArr1= Arrays.copyOfRange(arr, 0, arr.length/2);
subArr2= Arrays.copyOfRange(arr, arr.length/2,arr.length);
int sum1=0;
int sum2=0;
int diffSum;

for (int i = 0; i < arr.length/2; i++) {
sum1=sum1 + subArr1[i];
sum2=sum2 + subArr2[i];
}
diffSum= Math.abs(sum1- sum2);
int temp=0;

for (int i = 0; i < arr.length/2; i++) {

for (int j = 0; j < subArr2.length; j++) {

if(sum1 > sum2){
if(subArr1[i] >subArr2[j]){

sum1=sum1- subArr1[i] + subArr2[j];
sum2=sum2- subArr2[j] + subArr1[i];
if(diffSum >= Math.abs(sum1- sum2)){
diffSum= Math.abs(sum1- sum2);
temp= subArr1[i];
subArr1[i]= subArr2[j];
subArr2[j]= temp;
}else{
sum1=sum1- subArr2[j] + subArr1[i];
sum2=sum2- subArr1[i] + subArr2[j];
}

}

}else if (sum1 < sum2){

if(subArr1[i]  < subArr2[j]){

sum1=sum1- subArr1[i] + subArr2[j];
sum2=sum2- subArr2[j] + subArr1[i];
if(diffSum >= Math.abs(sum1- sum2)){
diffSum= Math.abs(sum1- sum2);
temp= subArr1[i];
subArr1[i]= subArr2[j];
subArr2[j]= temp;
}else{
sum1=sum1- subArr2[j] + subArr1[i];
sum2=sum2- subArr1[i] + subArr2[j];
}

}
}
else {
break;
}

}

}
for (int i = 0; i < subArr1.length; i++) {
System.out.print(" "+subArr1[i]);
}
System.out.print("   sum is "+ sum1);

System.out.print("        second array");
for (int i = 0; i < subArr2.length; i++) {
System.out.print(" "+subArr2[i]);
}
System.out.print("   sum is "+ sum2);
System.out.println("  difference is "+ diffSum);
}
}
Similar Questions

Input:
[1 7 15 29 11 9]

Output:
[9 15] [1 7 11 29]

Average of first part: (15+9)/2 = 12,
Average of second part: (1 + 7 + 11 + 29) / 4 = 12

You have a 2D matrix. Only two ZEROs in matrix.
Find the path from 1st zero to 2nd zero with least sum.

``````1       6       8       9       0       3

4       9       -5      5       11      13

8       9       44      23      15      -20

7       9       7       -13     14      11

0       16      23      31      16      7

67      5       4       23      21      19
``````

``````1       6       8       9       0  ----> 3
|
4       9       -5      5       11      13
|
8       9       44      23      15      -20
|
7 <---- 9 <---- 7 <--- -13 <--- 14 <---  11
|
0       16      23      31      16        7

67      5       4       23      21       19
``````
``````An array of positive and negative number is given.
Find out the subarray which have maximum sum.

Input =>  1   -2   5   -9    4    11    3    -9
Output =>  4, 11,  3    SUM = 18

Input =>    1    -4    5     9    -1     -9    19     9    0    5    -11   -10   38
Output =>   5, 9, -1, -9 ,19, 9, 0, 5, -11, -10, 38       sum = 54
``````

Convert the given string into palindrome with minimum number of appends(at end of the given string). O(n) algorithm will be appreciated ??

Input :=> Malayal
Output :=> Malayalam