CareerCup

Here is the solution for finding minimum difference after dividing the array in to two halfs. Some book keeping to this can also give the two sub arrays. The idea is to recursively divide the array in to two half by considering two things
1. The i'th number belongs to first partition
2. The ith number belongs to second partition.
Finally the best solution is the one that returns minimum difference

#include <stdio.h>
#include <vector>
using namespace std;
#define MIN(x, y) ( (x < y) ? x : y)

int abs(int x) {
  return ((x < 0) ? (-1*x) : x);
}

int divide(vector<int> a, int i, int X, int Y) {
  if(i >= a.size()) {
    return abs(X-Y);
  } else {
    int x1 = divide(a, i+1, X+a[i], Y);
    int x2 = divide(a, i+1, X, Y+a[i]);
    return min(x1, x2);
  }
}

int main() {
  int N;
  scanf("%d", &N);
  vector<int> a;
  int N_ = N;
  while(N_--) {
    int x; 
    scanf("%d", &x);
    a.push_back(x);
  } 
  printf("Min diff : %d\n", divide(a, 0, 0, 0));
}

int mina1[100];
int n1;
int mina2[100];
int n2;

void getsub(int a[],int n,int a1[],int ind1,int a2[],int ind2,int sum1,int sum2,int *min)
{
     if(n==0)
     {
        if(sum1>sum2)
        {
           if(sum1-sum2<*min)
           {
              *min=sum1-sum2;
              int i=0;
              for(i=0;i<ind1;i++)
                 mina1[i]=a1[i];
              n1=ind1;
              for(i=0;i<ind2;i++)
                 mina2[i]=a2[i];
              n2=ind2;
           }
        }
        else
        {
           if(sum2-sum1<*min)
           {
              *min=sum2-sum1;
              int i=0;
              for(i=0;i<ind1;i++)
                 mina1[i]=a1[i];
              n1=ind1;
              for(i=0;i<ind2;i++)
                 mina2[i]=a2[i];
              n2=ind2;
           }
        }
        return;
     }
     a1[ind1]=a[n-1];
     getsub(a,n-1,a1,ind1+1,a2,ind2,sum1+a[n-1],sum2,min);
     a2[ind2]=a[n-1];
     getsub(a,n-1,a1,ind1,a2,ind2+1,sum1,sum2+a[n-1],min);
}

I dont know what "not necessary to be continuous" means. This one is straight forward. The algorithm is create an empty array maintain the minimum difference by adding all the values to begin with. After that loop through the array and maintain current difference value and compare it with the minimum difference value. As soon as the current difference exceeds the minimum difference, break the loop.

Here is the working java code:

public void minDiff()
    {
        List<Integer> arr1 = new ArrayList<Integer>();
        arr1.add(3);
        arr1.add(8);
        arr1.add(9);
        arr1.add(6);
        arr1.add(11);
        arr1.add(15);
        arr1.add(1);
        arr1.add(2);
        arr1.add(3);
        
        
        ArrayList<Integer> arr2 = new ArrayList<Integer>();
        Integer minDiff = 0;
        Integer currDiff = 0;
        Integer minIndex = 0;
        Integer currIndex = 0;
        for(int i=0;i < arr1.size();i++)
        {
            minDiff += arr1.get(i);
        }
        currDiff = minDiff;
        
        for(int j = arr1.size()-1;j >= 0; j--)
        {
            currDiff = currDiff - (2*arr1.get(j));
            if(Math.abs(currDiff) <= minDiff)
            {
                minDiff = Math.abs(currDiff);
                minIndex = j;
                arr2.add(arr1.get(j));
                arr1.remove(j);
            }
            else
            {
                break;
            }
        }
        

        System.out.println(arr1.toString() + "," + arr2.toString());
        System.out.println(minIndex);
        
        
    }

I dont know what "not necessary to be continuous" means. This one is straight forward. The algorithm is create an empty array maintain the minimum difference by adding all the values to begin with. After that loop through the array and maintain current difference value and compare it with the minimum difference value. As soon as the current difference exceeds the minimum difference, break the loop.

Here is the working java code:

public void minDiff()
    {
        List<Integer> arr1 = new ArrayList<Integer>();
        arr1.add(3);
        arr1.add(8);
        arr1.add(9);
        arr1.add(6);
        arr1.add(11);
        arr1.add(15);
        arr1.add(1);
        arr1.add(2);
        arr1.add(3);
        
        
        ArrayList<Integer> arr2 = new ArrayList<Integer>();
        Integer minDiff = 0;
        Integer currDiff = 0;
        Integer minIndex = 0;
        Integer currIndex = 0;
        for(int i=0;i < arr1.size();i++)
        {
            minDiff += arr1.get(i);
        }
        currDiff = minDiff;
        
        for(int j = arr1.size()-1;j >= 0; j--)
        {
            currDiff = currDiff - (2*arr1.get(j));
            if(Math.abs(currDiff) <= minDiff)
            {
                minDiff = Math.abs(currDiff);
                minIndex = j;
                arr2.add(arr1.get(j));
                arr1.remove(j);
            }
            else
            {
                break;
            }
        }
        

        System.out.println(arr1.toString() + "," + arr2.toString());
        System.out.println(minIndex);
        
        
    }

I think this problem can be converted into this:
The sum of the array is A, and find a subset which sum is most nearest to or equal to A. So the problem can be solved by DP.
But it required recursive code.

May be I misunderstood something but looks like the task is pretty easy if input array is sorted in descendant order especially using recursion:

import Data.List (sort)  
-- 
findSubarrays ::(Num a, Ord a) =>  [a] -> ([a],[a])
findSubarrays x = divideSorted (reverse $ sort x) 0 0 ([],[])

divideSorted ::(Num a, Ord a) =>  [a] -> a -> a -> ([a], [a]) -> ([a],[a])
divideSorted [] _ _ (f,s) = (f,s)
divideSorted (x:y:xs) 0 0 ([],[]) = divideSorted xs x y ([x], [y])
divideSorted (x:xs) fcnt scnt (f,s) = 
	let firstIsLarger = (fcnt + x) > (scnt + x)
 	in if firstIsLarger then divideSorted xs fcnt (scnt+x) (f, s ++ [x]) 
 	   else divideSorted xs (fcnt+x) scnt (f ++ [x], s)

caculate the mean take the ceil value and then find a array of elements which will closest to mean (sum array - mean).

int divide(int[] a, int i, int X, int Y) {
		  if(i >= a.length) {
		    return Math.abs(X-Y);
		  } else {
		    int x1 = divide(a, i+1, X+a[i], Y);
		    int x2 = divide(a, i+1, X, Y+a[i]);
		    return Math.min(x1, x2);
		  }
	}

Not getting your code.Why are subtracting the currentdiff with 2times the value and then exchanging the mindiff and curentdiff.