top button
Flag Notify
    Connect to us
      Facebook Login
      Site Registration Why to Join

Facebook Login
Site Registration

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

+8 votes
2,521 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 by Prakash Singh

Share this question
Facebook Share Button Twitter Share Button Google+ Share Button LinkedIn Share Button Multiple Social Share Button
prakash, can you share example ? am not able catch this.

2 Answers

+2 votes
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
answer Nov 17, 2013 by Vikas Upadhyay
Thanks in advanced If some one can reduce the complexity.
0 votes

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
+3 votes

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

+7 votes

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

Answer

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
+5 votes
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
+8 votes

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

+2 votes

1,1,2,2,2,6,6,6,7,7,7,7,7,7,7,8,8,9,9,9

Example:
Input = 1 Output=0 (First index of 1).
Input = 2 Output=2 (First index of 2).
Input = 6 Output= 5 (First index of 6).
Input = 7 Output= 8 (First index of 7).
Input = 8 Output=15 (First index of 8).
Input = 9 Output=17 (First index of 9).

Contact Us
+91 9880187415
sales@queryhome.net
support@queryhome.net
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Bangalore-560102
Karnataka INDIA.
QUERY HOME
...