CareerCup

Partition problem .It is similar to finding whether we can get sum/2 value using arr.size()/2 elements. This can be solved using recursion or DP. The recursive Function call will be rec(0,arr.size()/2,sum/2);
where arr is the given array ,
sum is total sum of all values in the array.
and memoize is just for avoiding recalculation.
If this function returns true then its possible to partition otherwise not.

vector<int> arr;
int memoize[100][100][100];
memset(memoize,-1,sizeof(memoize)); //Initialise the array to -1
bool rec(int pos,int rem,int sum)
{
     if(sum<0) return false;
     if(pos>=arr.size())
          return (rem==0 && sum == 0);
     if(memoize[pos][rem][sum] != -1) // already computed
          return memoize[pos][rem][sum];
     return memoize[pos][rem][sum]=rec(pos+1,rem-1,sum-arr[pos]) || rec(pos+1,rem,sum );
}

Unlike the general partition problem, this one asks specifically for two sublists of equal length. At the very least, this allows the problem to be solved in polynomial time, as the untested Python below shows:

def sublists(a, n):
    if n == 0:
        return [[]]
    elif len(a) == 0:
        return []
    else:
        return sublists(a[1:], n) + [[a[0]] + s for s in sublists(a[1:], n - 1)]


def partition(a):
    if len(a) % 2 != 0:
        return None

    halves = sublists(a, len(a) / 2)
    total = sum(a)
    for half in halves:
        if sum(half) == total / 2:
            other_half = list(a)
            for x in half:
                other_half.remove(x)
            return (half, other_half)

    return None

However, I am undecided yet if it can be solved more optimally.

This can be done using subset sum problem

bool dp[sum/2];
memset(dp, sizeof(dp), 0);
dp[0] = 1;
int usingElements[sum/2];
memset(usingElements, sizeof(usingElements),0);

bool findEqualSum(vector<int> arr) {
	int len = arr.size();
	int sum = 0;
	for(int i=0; i<len; ++i) {
		sum += arr[i];	
	}

	for(int i=0; i<len; ++i) {
	for(int j=sum/2; j>=0; --j) {
		if(dp[j]==true && j+arr[i] <= sum/2 && usingElements[j] < len/2) {
			dp[j+arr[i]] = true;
			usingElements[j+arr[i]] = usingElements[j] + 1;
		}
		if(dp[sum/2] == true && usingElements[sum/2] == len/2)
			return true;
	}	
	}
	return false;
}

StackOverflow question #5898104. There is no great answer there though.

I think this question asks to divide the array in two equal halves with equal number of elements and equal sum that's why it says that array length is even. If this is the case just sort the array and pick alternate elements. that will give two arrays with equal number of elements and sum.

Solution in O(n):

Output:
3
1
1
2
2
1
4
9
3
2
9
1
sum(A)38
sum(B)20
sum(C)18

/* 
Problem:

Given an unsorted array, how to divide them into two equal arrays whose 
sum of difference is minimum. 
Can it be done in O(n)? 
*/

#include <iostream>
#include <vector>
#include <cstdlib>
#include <vector>
#include <algorithm>

void print_vector(const std::vector<int> &A) 
{
    for(auto it = A.cbegin(); it != A.cend(); ++it) {
		std::cout << *it << std::endl;
    }
}

int sum_of_elements(const std::vector<int>&A)
{
    int sum_of_elements = 0;
    for(int n: A) {
		sum_of_elements += n;
    }
    return sum_of_elements;
}

class Result {
public: 
    Result(int n) : vec(n), sum{0}, average{0} {
		it = vec.begin();
    }

    int check_sum(int value) {
		return sum + value;
    }

    bool is_value_greater_then_average(int value) {
		return value > average;
    }

    bool add(int value) {
		if(it == vec.end())
		    return false;
	
		*it = value;
		sum += value;
		++it;
	
		average += sum;
		if(vec.size() > 1)
		    average /= 2;
	
		return true;
    }

    int result() {
		return sum;
    }

private:
    std::vector<int> vec;
    std::vector<int>::iterator it;
    int sum;
    int average;
};

int main(int argc, char ** argv)
{
    //std::vector<int> A {1000, 1, 1, 1, 1, 1000};
    std::vector<int> A {3, 1, 1, 2, 2, 1, 4, 9, 3, 2, 9, 1};
    Result B(A.size()/2);
    Result C(A.size()/2);

    // O(n)
    for(auto itA = A.begin(); itA != A.end(); ++itA) {
	std::cout << *itA << std::endl;

	if(B.check_sum(*itA) > C.check_sum(*itA)) {
	    if(C.is_value_greater_then_average(*itA)) {
		if(C.add(*itA) != true)
		    B.add(*itA);
	    } else {
		if(B.add(*itA) != true)
		    C.add(*itA);
	    }
	} else {
	    if(B.is_value_greater_then_average(*itA)) {
		if(B.add(*itA) != true)
		    C.add(*itA);
	    } else {
		if(B.add(*itA) != true) 
		    C.add(*itA);
	    }
	}
    }

    std::cout << "sum(A)" << sum_of_elements(A) << std::endl;
    std::cout << "sum(B)" << B.result() << std::endl;
    std::cout << "sum(C)" << C.result() << std::endl;

    return 0;
}

I gave it a go in javascript.

I assumed that this statement, which is given in an answer above, is correct:
´´´I think this question asks to divide the array in two equal halves with equal number of elements and equal sum that's why it says that array length is even´´´

This solution uses bruteforce and it is not optimized.

var source = [1,2,3,4,5,3,6,2];
splitToEqualValue(source);


function splitToEqualValue(source){
  var halfSum = sum(source) / 2;
  var equalParts =  getVariants(source, source.length / 2).filter(function(variant){
    return halfSum == sum(variant)
  });
  return equalParts; // a list that contains one of the equal pairs
}

function getVariants(source, length){
  var variants = [];
  if (length < 1 ) return [[]];
  if (length > source.length ) length =  source.length;
  
  source.forEach(function(left, leftIndex){
    var right = unpick(source,leftIndex);

    var variantsOfRight = getVariants(right, length - 1).map(function(variant){
      variant.unshift(left);
      return variant;
    })

    // TODO Instead of bulk insert, do it one by one 
    // and if there is a duplicate(eg. same array different order dont add it)
    variants = variants.concat(variantsOfRight);
  })

  return variants;
}

function sum(source){
  return source.reduce(function(previousValue, currentValue, index, array){
    return previousValue + currentValue;
  });
}

function unpick(source, needleIndex){
    return source.filter(function(elm, elmIndex){
        return needleIndex != elmIndex;
    })
}

Here is a C implementation, which is an O(n^2) algorithm, the first step is calc the difference between two array, and then, if the sum of the difference array is not zero, you pick the closet element around the value of half of the total difference, keep going. As long as the partition is possible, you will reach the point that sum difference is zero in at most n steps.

#include <stdio.h>

#define asize 20

int input_array[asize] = {1	,	11	,
			  2	,	12	,
			  3	,	13	,
			  4	,	14	,
			  5	,	15	,
			  6	,	16	,
			  7	,	17	,
			  8	,	18	,
			  9	,	19	,
			  155,	65};

#define ABS(x) ((x) > 0 ? (x) : (-(x)))

int find_closest(int* in, int size, int value)
{
  int i, diff, idx=0;
  unsigned int min_diff = (unsigned)-1;
 
  for(i=0;i<size;i++){
    diff = in[i] - value;
    diff = ABS(diff);
    if(min_diff > diff){
      min_diff = diff;
      idx = i;
    }
  }
  return idx;
}

void print_vect(char* name, int* array, int size)
{
  int i;
  printf("%s = [ ", name);
  for(i=0;i<size;i++) printf("%d ", array[i]);
  printf("]\n");
}
    
int main( int argc, char* argv[])
{
  int sum = 0;
  int i,idx;
  int left[asize/2], right[asize/2], diff[asize/2];
  int lsum, rsum, tmp, dsum;


  //partition arbitrarily
  for(i=0;i<asize;i++){
    sum += input_array[i];
    if(i < asize/2) left[i] = input_array[i];
    else right[i-asize/2] = input_array[i];
  }  

  printf("Before sorting\n");
  print_vect("left", &left[0], asize/2);
  print_vect("right", &right[0], asize/2);
  
  lsum = 0;
  rsum = 0;
  for(i=0;i<asize/2;i++){
    lsum += left[i];
    rsum += right[i];
    diff[i] = left[i] - right[i];
  }
  dsum = lsum - rsum;

  //at most N/2 
  do{

    if(dsum == 0)
      break;

    //At most N/2
    idx = find_closest(&diff[0], asize/2, dsum/2);
    printf("dsum: %d, closet: diff[%d] = %d\n", dsum, idx, diff[idx]);
    
    //swap left and right and do again
    tmp = left[idx];
    left[idx] = right[idx];
    right[idx] = tmp;
    
    dsum -= diff[idx];
  }while(1);

  printf("after sorting\n");
  print_vect("left", &left[0], asize/2);
  print_vect("right", &right[0], asize/2);

  return 0;
}

Brute force C++ using recursion, but sped up considerably by sorting the array before hand.

bool FindHalf(const vector<int> &A, int target, int remaining, 
int start, vector<bool> used, vector<int> &first_half, vector<int> &second_half)
{
    //g_calls++;

    if(target == 0 && remaining == 0) {
        for(size_t i=0; i < used.size(); i++) {
            if(used[i])
                first_half.push_back(A[i]);
            else
                second_half.push_back(A[i]);
        }

        return true;
    }

    // Did not find a solution
    if(remaining == 0)
        return false;

    for(size_t i=start; i < A.size(); i++) {
        if(used[i]) continue;

        if(target - A[i] >= 0) {
            used[i] = true;

            if(FindHalf(A, target - A[i], remaining-1, i+1, used, first_half, second_half))
                return true;

            used[i] = false;
        }
    }

    return false;
}

// wrapper function
void FindHalf(const vector<int> &A)
{
    assert(A.size() % 2 == 0);

    int sum = accumulate(A.begin(), A.end(), 0);
    int target = sum/2;

    vector<bool> used(A.size(), false);
    vector<int> first_half, second_half;

    FindHalf(A, target, A.size()/2, 0,used, first_half, second_half);

    // print out results
    for(size_t i=0; i < first_half.size(); i++)
        cout << first_half[i] << " ";
    cout << endl;

    for(size_t i=0; i < second_half.size(); i++)
        cout << second_half[i] << " ";
    cout << endl;
}

// Example of usage
int main()
{
    vector<int> A = {1,11,2,12,3,13,4,14,5,15,6,16,7,17,8,18,9,19,
155,65,1,11,2,12,3,13,4,14,5,15,6,16,7,17,8,18,9,19,155,65}; // C++11

    sort(A.begin(), A.end());
    FindHalf(A);

    return 0;
}

With the example input of 40 integers, it makes 271 recursive calls to FindHalf. Without the sorting it takes a VERY long time.

int[] a = {7,5,4,1,1,2};
		
		Arrays.sort(a);
		
		int[] a1 = new int[a.length /2];
		int[] a2 = new int[a.length /2];
		
		int i =0;
		int j = a.length -1;
		
		boolean b = true;
		int k1 =0;
		int k2 =0;
		while(i<j-1) {
			if(b) {
				a1[k1++] = a[i];
				a1[k1++] = a[j];
				b = false;
			}else {
				a2[k2++] = a[i];
				a2[k2++] = a[j];
				b = true;
			}
			
			i++;
			j--;
			
		}
		
		if(b) {
			a1[k1] = a[i];
			a2[k2] = a[j];
		}else {
			a2[k1] = a[i];
			a1[k2] = a[j];
		}
		
	
		System.out.println(Arrays.toString(a1));
		System.out.println(Arrays.toString(a2));

You can use either dfs + memorization or 3d DP to resolve the issue. The time complexity is O((n^2)sum), while sum is the sum of all elements in the array.

I don't think this one have O(n*sum) solution -- unless we remove the restriction of evenly splitting the array.

the problem of partitioning array in equal halves with minimum sum difference I think can be solved in O(NlogN)+O(N) time. first sort the array in ascending order. Since length of array is even, assign value with odd index to set #1, value with even index to set #2. increase iterative step by two and apply reverse process.

static int min_partition(int[] a)
	{
		sort(a); //sort the array in ascending order
		//declare two sets. This may be done in place BTW if additional space can not be used
		int []s1 = new int[a.length/2];
		int []s2 = new int[a.length/2];
		int i=0, ind=1, x=0;
		while (i<=a.length-2)
		{
			if (ind%2==1)
			{
				s1[x]=a[i];
				s2[x]=a[i+1];
			}
			else
			{
				s1[x]=a[i+1];
				s2[x]=a[i];
			}
		 ind++;
		 i=i+2;
		 x++;
		}
		
	 return sumDiff(s1, s2); //returns minimum sum difference of two halves
	}

A brute force solution in Java, where we create all possible subsets of array.length/2 size until we find sum = sum(array)/2 or all sets were evaluated

public class DivideArrayInEqualSides {

	public static void main(String args[]) {
		int[] arr = {5, 5, 5, 5, 1, 1};
		System.out.println(canDivide(arr));
	}
	
	public static boolean canDivide(int[] arr) {
	  int sum = 0;
	  for (int idx = 0; idx < arr.length; idx++) {
	    sum += arr[idx];
	  }
	  if (sum % 2 != 0) {
	    return false;
	  }
	  
	  return subset(arr, 0, 0, 0, sum/2);
	}

	public static boolean subset(int[] arr, int nextIdx, int idxUsed, int currSum, int targetSum) {
	  currSum += arr[nextIdx];
	  idxUsed++;
	  
	  if (idxUsed == arr.length/2) {
	    return currSum == targetSum;
	  }
	  
	  boolean isSubset = false;
	  for (int count = 1; count < arr.length - nextIdx; count++) {
	    isSubset = subset(arr, nextIdx + count, idxUsed, currSum, targetSum);
	    if (isSubset) {
	    	if (idxUsed == arr.length/2 -1) {
	    		System.out.println(nextIdx+count);
	    	}
	    	System.out.println(nextIdx);
	    	break;
	    }
	  }
	  return isSubset;
	}

}

1. Find sum, say S
2. find all subsets
3. select ones with length n/2 where n is number of elements in first array
4. from list in 3 select one whose sum matches S/2

A solution in n + n*logn.
Sort the array descending.
Take each input element and add it to the half that has it's missing average closer to it.
missing average means: sum required to reach the target value divided by the number of empty slots.

/// <summary>
        /// You are given an array, divide it into 2 equal halves such that the sum of those 2 halves are equal.
        /// (Imagine that such division is possible for the input array and array size is even)
        /// </summary>
        /// <param name="inputArray"></param>
        public static void Solve(List<int> inputArray)
        {
            inputArray = inputArray.OrderByDescending(a => a).ToList();
            var a1 = new int[inputArray.Count / 2];
            var a2 = new int[inputArray.Count / 2];

            var targetSum = inputArray.Sum() / 2;
            int a1Sum = 0, a2Sum = 0, a1Idx = 0, a2Idx = 0;
            foreach (var elem in inputArray)
            {
                var a1avg = (targetSum - a1Sum) / (float)(a1.Length - a1Idx + 1);
                var a2avg = (targetSum - a2Sum) / (float)(a2.Length - a2Idx + 1);
                if (elem - a1avg < elem - a2avg)
                {
                    a1[a1Idx++] = elem;
                    a1Sum += elem;
                }
                else
                {
                    a2[a2Idx++] = elem;
                    a2Sum += elem;
                }
            }

            WriteLine(a1);
            WriteLine(a2);
        }

In the unlikely event that the two halves are to be contiguous, you could double the array length, take partial sums from the beginning, wrapping around the original array while continuing straight ahead in the doubled, partial-sum one. Then, walk the doubled array taking the difference between the elements sizeof(original array) = N apart. When you hit a difference of sum / 2, back-translate to indexes of the original array. The doubled array is just to avoid fiddling with % N. And yeah, this interpretation is too easy.

Hmm; if there are any duplicates you can remove them to your two halves, without thinking any further about them, and solve the reduced problem. The remaining numbers are all unique. Not sure how to use that though. (No this is junk, eg 3,1,5,3 would be 3,3 and 1,5.)

It's like the 0/1 knapsack problem, you have to fill your knapsack with weights (= values) of sum / 2. Except, that the number of items you can take is constrained, too; hum...

An O(n^2) solution.
1)Find the sum of elements of entire array
2)Based on the given assumption now find the subset of elements which add upto sum/2.
3)print the elements that are in subset as 1st half and print the elements that are not as 2nd half.

There is a dynamic programming algorithm for finding the subset in O(n^2) time.So the time complexity could be O(n^2).

Another way is to use backtracking which would be O(2^n)

main()
{
    printf("Hello World")
}