Google Interview Question
Software EngineersCountry: United States
1. find the sum/2 of the array, which is the "goal"
2. have two index: start; end. have two variable: currsum; mindif=goal;
3. sort the array
4. loop the array, add array[start] to currsum, if |goal-currsum|<mindif, then start++; add array[end] to currsum, if |goal-currsum|<mindif, then end++; if both are >mindif. return start and end.
5. cut the array start-end as one partition, rest as the other
#include<iostream>
#include <math.h>
#include<vector>
#include<algorithm>
using namespace std;
int sum(vector<int> &vec) {
int sum_ = 0;
for(vector<int>::iterator iter = vec.begin(); iter != vec.end(); iter++) {
sum_ += *iter;
}
return sum_;
}
void divide_min_diff(vector<int> *arr) {
sort(arr->begin(), arr->end());
int x = arr->size() / 2;
vector<int> first(arr->begin(), arr->begin() + x);
vector<int> second(arr->begin() + x, arr->end());
vector<int>::reverse_iterator riter;
vector<int>::iterator iter;
iter = first.begin();
riter = second.rbegin();
while (iter != first.end() && riter != second.rend()) {
int diff = sum(second) - sum(first);
if ((*riter - *iter) < diff) {
iter_swap(iter, riter);
}
iter++;
riter++;
}
for (std::vector<int>::const_iterator i = first.begin(); i != first.end(); ++i)
std::cout << *i << ' ';
cout << "Second" << endl;
for (std::vector<int>::const_iterator i = second.begin(); i != second.end(); ++i)
std::cout << *i << ' ';
}
int main(void) {
vector<int> arr;
arr.push_back(1);
arr.push_back(2);
arr.push_back(9);
arr.push_back(7);
arr.push_back(6);
arr.push_back(3);
arr.push_back(8);
divide_min_diff(&arr);
getchar();
return 1;
}
Sort the array
divide the array
get the sum of the first half
get the sum of the second half
diff = sum(first)-sum(second)
chose the first element in the first half
Chose the last element in the second half
if last - first < diff
swap the elements in the first element of first half with the last of the second half
let array be 182396
sort 1236897
divide into two arrays
123 6789
diff = 24
9-1 < 24
swap 9 and 1
923 6781
diff = 8
8-2 < diff
swap 8 and 2
983 6721
diff = 4
7-3 is not less than 4 .. so no need to swap
Continue until one of the array completes.
for the given input 1236897 your code returns 9 8 3 and 6 7 2 1 which has s1 = 20 s2 = 16 and diff = 4. however 9 7 3 and 6 8 2 1 have s1 = 19 s2 = 17 and diff = 2. so your algorithm is not correct.
Probably, you need to re-sort the sub-arrays, or scan through the sub-arrays to find the swap pair.
@Ravi - in this case the output will be (983 6721) and the difference between the sum of two partitions will be 4 which is not minimum. The minimum difference that can be achieved with your test case is 0 (981 6723)
yeah, he is right, this algorithm is flawed, can someone give some idea how to correct it?
Based on Ravi peri's answer. Corrected the error case .
import java.util.Arrays;
/**
*
* @author Arpit
*/
public class DivideMinDiff {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 6, 8, 9, 7};
new DivideMinDiff().partition(arr);
}
public void partition(int[] arr) {
Arrays.sort(arr);
int[] arr1 = new int[(int) Math.floor(arr.length / 2)];
int[] arr2 = new int[(int) Math.ceil(arr.length / 2) + 1];
int counter = 0;
for (int i = 0; i < arr1.length; i++) {
arr1[i] = arr[counter++];
}
for (int i = 0; i < arr2.length; i++) {
arr2[i] = arr[counter++];
}
int leftSum = sum(arr1);
int rightSum = sum(arr2);
int diff = Math.abs(leftSum - rightSum);
int left = 0;
int mid = arr1.length - 1;
int right = arr2.length - 1;
while ((left <= arr1.length - 1) && (right >= 0)) {
int leftDif = ((leftSum - arr1[left]) + arr2[right]);
int rghtDif = ((rightSum - arr2[right]) + arr1[left]);
if (Math.abs(leftDif - rghtDif) <= diff) {
leftSum = leftSum - arr1[left] + arr2[right];
rightSum = rightSum - arr2[right] + arr1[left];
diff = Math.abs(leftSum - rightSum);
int temp = arr1[left];
arr1[left] = arr2[right];
arr2[right] = temp;
left++;
right = arr2.length - 1;
} else {
if (Math.abs(leftDif - rghtDif) > diff) {
right--;
}
}
}
for (int a : arr1) {
System.out.print(a + " ");
}
System.out.println("");
for (int a : arr2) {
System.out.print(a + " ");
}
System.out.println("");
}
private int sum(int[] arr) {
int count = 0;
for (int a : arr) {
count += a;
}
return count;
}
}
#include<iostream>
#include <math.h>
#include<vector>
#include<algorithm>
using namespace std;
int sum(vector<int> &vec) {
int sum_ = 0;
for(vector<int>::iterator iter = vec.begin(); iter != vec.end(); iter++) {
sum_ += *iter;
}
return sum_;
}
void divide_min_diff(vector<int> *arr) {
sort(arr->begin(), arr->end());
int x = arr->size() / 2;
vector<int> first(arr->begin(), arr->begin() + x);
vector<int> second(arr->begin() + x, arr->end());
vector<int>::reverse_iterator riter;
vector<int>::iterator iter;
iter = first.begin();
riter = second.rbegin();
while (iter != first.end() && riter != second.rend()) {
int diff = sum(second) - sum(first);
if ((*riter - *iter) < diff) {
iter_swap(iter, riter);
}
iter++;
riter++;
}
for (std::vector<int>::const_iterator i = first.begin(); i != first.end(); ++i)
std::cout << *i << ' ';
cout << "Second" << endl;
for (std::vector<int>::const_iterator i = second.begin(); i != second.end(); ++i)
std::cout << *i << ' ';
}
int main(void) {
vector<int> arr;
arr.push_back(1);
arr.push_back(2);
arr.push_back(9);
arr.push_back(7);
arr.push_back(6);
arr.push_back(3);
arr.push_back(8);
divide_min_diff(&arr);
getchar();
return 1;
}
Sort the numbers in ascending order. Keep two pointers at start+1 and end-1 and swap them.
Eg: arr[] = {5,7,50,8,9,62)
sort: arr= {5,7,8,9,50,62}
Set A[] = {5,50,9}
Set B[] = {8,7,62}
Have two empty vectors and two variable representing the sum of integers in each vector. sort the input vector in descending order. While input vector is not empty, if length of input vector > 1, pop 2 numbers. Add the bigger to the vector with lower sum, and add the other to the vector with highr sum. If lenght input vector == 1, pop 1 and add the number to the vector with lower sum. And repeat until empty.
1. Sort array
2. Add first and last in set1
3. Similarly, second and secondlast in set2
4. for num%4!=0, handle these spl cases.
Complexity - O(nlogn)
import java.util.*;
public class HelloWorld{
public static void main(String []args){
int[] arr = {1,4, 3, 2,100};
System.out.println(f(arr));
}
public static List<List<Integer>> f(int[] arr){
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(arr);
List<Integer> setA= new ArrayList<>();
List<Integer> setB= new ArrayList<>();
int countA=0, countB=0;
list.add(setA);
list.add(setB);
int n = arr.length;
int i=0;
for(; i<(n/4)*2; i++){
if(i%2 ==0){
setA.add(arr[i]);
setA.add(arr[n-(i+1)]);
countA+= arr[i] + arr[n-(i+1)];
} else{
setB.add(arr[i]);
setB.add(arr[n-(i+1)]);
countB+= arr[i] + arr[n-(i+1)];
}
}
int rem= n%4;
if(rem==1){
if(countA<countB){
setA.add(arr[i]);
} else{
setB.add(arr[i]);
}
return list;
}
if(rem==2){
if(countA<countB){
setB.add(arr[i]);
setA.add(arr[i+1]);
} else{
setA.add(arr[i]);
setB.add(arr[i+1]);
}
return list;
}
if(rem==3){
if(countA<countB){
setA.add(arr[i+2]);
countA+=arr[i+2];
if(countA<countB){
setB.add(arr[i]);
setA.add(arr[i+1]);
} else{
setA.add(arr[i]);
setB.add(arr[i+1]);
}
} else{
setB.add(arr[i+2]);
countB+=arr[i+2];
if(countB<countA){
setA.add(arr[i]);
setB.add(arr[i+1]);
} else{
setB.add(arr[i]);
setA.add(arr[i+1]);
}
}
return list;
}
return list;
}
}
def partition(A):
A.sort()
for i in range(1, len(A)/2, 2):
A[i], A[-1-(i - 1)] = A[-1 - (i - 1)], A[i]
if len(A) % 2 and sum(A[0:len(A)/2]) < sum(A[len(A)/2 + 1:]):
return A[:len(A)/2 + 1], A[len(A)/2 + 1:]
else:
return A[:len(A)/2], A[len(A)/2:]
It is subset sum problem. Find elements of array that can have sum close to N/2 where N is sum of all elements of the array
What if we create a heap and put every next element from heap into array one and array two alternatively. Wont that create two arrays having min diff. Its same as from sorted array pick even index element in one array and odd index in another and difference will be min
/*Given an array consisting of N Numbers.
Divide it into two Equal(it is important) partitions such that difference between sum of both partitions is minimum.
If number of elements are odd difference in partition size can be at most 1.*/
package com.cxy.test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Random;
public class TestOne {
public static void main(String[] args) {
/*Integer[] testArray = new Integer[10];;
for (int i =0;i<10;i++)
{
Random rn=new Random();
testArray[i]=rn.nextInt(100);
}*/
Integer[] testArray={1,2,3,6,8,9,7};
ArrayList<Integer> array1 = new ArrayList<Integer>();
ArrayList<Integer> array2 = new ArrayList<Integer>();
Arrays.sort(testArray, Collections.reverseOrder());
for (int i = 0; i < testArray.length/2; i++) {
array1.add(testArray[i]);
}
for (int i = testArray.length/2; i < testArray.length; i++) {
array2.add(testArray[i]);
}
int arrayDifference = sum(array1)-sum(array2);
if(arrayDifference !=0)
{
array1= new ArrayList<Integer>();
array2= new ArrayList<Integer>();
for (int i = 0; i < testArray.length; i++) {
if (i ==0) {
array1.add(testArray[i]);
}
else if (i==1) {
array2.add(testArray[i]);
}
else
{
int sum1=sum(array1);
int sum2=sum(array2);
if(i<=testArray.length-2 || testArray.length%2==1)
{
if(array1.size() - array2.size() >1)
{
array2.add(testArray[i]);
}
else if(array2.size() - array1.size() >1)
{
array1.add(testArray[i]);
}
else
{
if (sum1 <= sum2)
{
array1.add(testArray[i]);
}
else
{
array2.add(testArray[i]);
}
}
}
else
{
if(array1.size() - array2.size() ==1)
{
array2.add(testArray[i]);
}
else if(array2.size() - array1.size() ==1)
{
array1.add(testArray[i]);
}
}
}
}
}
System.out.println(Arrays.toString(testArray));
printList(array1);
System.out.println(sum(array1));
printList(array2);
System.out.println(sum(array2));
}
public static int sumArray(Integer[] tempArray) {
int sum = 0;
for (int i : tempArray)
sum += i;
return sum;
}
public static int sum(ArrayList<Integer> tempArrayList) {
int sum = 0;
for (Integer i : tempArrayList)
sum += i;
return sum;
}
public static void printList(ArrayList<Integer> list) {
String x = "";
for (Integer elem : list) {
x += elem + ",";
}
System.out.print(x+" | Sum is:");
}
}
/*Given an array consisting of N Numbers.
Divide it into two Equal(it is important) partitions such that difference between sum of both partitions is minimum.
If number of elements are odd difference in partition size can be at most 1.*/
package com.cxy.test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Random;
public class TestOne {
public static void main(String[] args) {
/*Integer[] testArray = new Integer[10];;
for (int i =0;i<10;i++)
{
Random rn=new Random();
testArray[i]=rn.nextInt(100);
}*/
Integer[] testArray={1,2,3,6,8,9,7};
ArrayList<Integer> array1 = new ArrayList<Integer>();
ArrayList<Integer> array2 = new ArrayList<Integer>();
Arrays.sort(testArray, Collections.reverseOrder());
for (int i = 0; i < testArray.length/2; i++) {
array1.add(testArray[i]);
}
for (int i = testArray.length/2; i < testArray.length; i++) {
array2.add(testArray[i]);
}
int arrayDifference = sum(array1)-sum(array2);
if(arrayDifference !=0)
{
array1= new ArrayList<Integer>();
array2= new ArrayList<Integer>();
for (int i = 0; i < testArray.length; i++) {
if (i ==0) {
array1.add(testArray[i]);
}
else if (i==1) {
array2.add(testArray[i]);
}
else
{
int sum1=sum(array1);
int sum2=sum(array2);
if(i<=testArray.length-2 || testArray.length%2==1)
{
if(array1.size() - array2.size() >1)
{
array2.add(testArray[i]);
}
else if(array2.size() - array1.size() >1)
{
array1.add(testArray[i]);
}
else
{
if (sum1 <= sum2)
{
array1.add(testArray[i]);
}
else
{
array2.add(testArray[i]);
}
}
}
else
{
if(array1.size() - array2.size() ==1)
{
array2.add(testArray[i]);
}
else if(array2.size() - array1.size() ==1)
{
array1.add(testArray[i]);
}
}
}
}
}
System.out.println(Arrays.toString(testArray));
printList(array1);
System.out.println(sum(array1));
printList(array2);
System.out.println(sum(array2));
}
public static int sumArray(Integer[] tempArray) {
int sum = 0;
for (int i : tempArray)
sum += i;
return sum;
}
public static int sum(ArrayList<Integer> tempArrayList) {
int sum = 0;
for (Integer i : tempArrayList)
sum += i;
return sum;
}
public static void printList(ArrayList<Integer> list) {
String x = "";
for (Integer elem : list) {
x += elem + ",";
}
System.out.print(x+" | Sum is:");
}
}
I just go through the array and test all subsets of length n/2, which have the minimum difference, this solution gives one of the sets indices, and once having one of the sets, as I found indices in a sorted order, I can easily find the second subset indices:
void findTwoSubset(const vector<int>&array,vector<int>&s,
vector<int>& solution, int start, int sum,
int total, int &diff) {
if(s.size()==array.size()/2) {
int sum1=sum;
int sum2=total-sum;
int d=fabs(sum1-sum2);
if(d<diff) {
solution=s;
diff=d;
}
return;
}
for(int i=start; i<array.size(); ++i) {
s.push_back(i);
findTwoSubset(array, s, solution, i+1, sum+array[i],total,diff);
s.pop_back();
}
}
void findTwoSubset(const vector<int>& array, vector<int> &s1, vector<int>& s2) {
int total=0;
for(int i=0; i<array.size(); ++i)
total+=array[i];
vector<int> solution;
int diff=INT_MAX;
findTwoSubset(array, s1, solution, 0, 0, total, diff);
s1=solution;
// finding the second subset elements as first subset elements are sorted in indices it is easy
int i=0;
int j=0;
while(i<s1.size()) {
if(j<s1[i]) { //before this index, push it to the result
s2.push_back(j);
j++;
}else if(s1[i]==j) {
i++;
j++;
}
}
// add everything after the last element
int end=s1[s1.size()-1];
for(int i=end+1; i<array.size(); ++i) {
s2.push_back(i);
}
}
int main() {
vector<int> array={1,2,3,6,7,8,9};
vector<int> s1;
vector<int> s2;
findTwoSubset(array, s1, s2);
for(int i=0; i<s1.size(); ++i)
cout<<array[s1[i]] << " ";
cout << endl;
for(int i=0; i<s2.size(); ++i)
cout<<array[s2[i]] << " ";
cout << endl;
return 0;
}
I updated my code with finding the second subset also:
void findTwoSubset(const vector<int>&array,vector<int>&s,
vector<int>& solution, int start, int sum,
int total, int &diff) {
if(s.size()==array.size()/2) {
int sum1=sum;
int sum2=total-sum;
int d=fabs(sum1-sum2);
if(d<diff) {
solution=s;
diff=d;
}
return;
}
for(int i=start; i<array.size(); ++i) {
s.push_back(i);
findTwoSubset(array, s, solution, i+1, sum+array[i],total,diff);
s.pop_back();
}
}
void findTwoSubset(const vector<int>& array, vector<int> &s1, vector<int>& s2) {
int total=0;
for(int i=0; i<array.size(); ++i)
total+=array[i];
vector<int> solution;
int diff=INT_MAX;
findTwoSubset(array, s1, solution, 0, 0, total, diff);
s1=solution;
// finding the second subset elements as first subset elements are sorted in indices it is easy
int i=0;
int j=0;
while(i<s1.size()) {
if(j<s1[i]) { //before this index, push it to the result
s2.push_back(j);
j++;
}else if(s1[i]==j) {
i++;
j++;
}
}
// add everything after the last element
int end=s1[s1.size()-1];
for(int i=end+1; i<array.size(); ++i) {
s2.push_back(i);
}
}
int main() {
vector<int> array={1,2,3,6,7,8,9};
vector<int> s1;
vector<int> s2;
findTwoSubset(array, s1, s2);
for(int i=0; i<s1.size(); ++i)
cout<<array[s1[i]] << " ";
cout << endl;
for(int i=0; i<s2.size(); ++i)
cout<<array[s2[i]] << " ";
cout << endl;
return 0;
}
Imagine that your state is something like this:
state(current element of the set, set A, set B)
In each step you have 2 possible scenarios:
1) Add the value to the set A
2) Add the value to the set B
void findTwoSubset(const vector<int>&array,vector<int>&s1, vector<int>& s2,
vector<int>& solution_s1, vector<int>& solution_s2,
int start, int sum1, int sum2, int& diff) {
int N=array.size();
if(start==N) {
bool condition=false;
if(N%2==0) {
if(s1.size()==N/2 && s2.size()==s1.size())
condition=true;
}else{
if(s1.size()==N/2 && s2.size()==N/2+1)
condition=true;
}
if(condition) {
int d=fabs(sum1-sum2);
if(d<diff) {
diff=d;
solution_s1=s1;
solution_s2=s2;
}
}
}
for(int i=start; i<N; ++i) {
if(s1.size()<(N/2)) {
s1.push_back(array[i]);
findTwoSubset(array,s1, s2,solution_s1, solution_s2,i+1, sum1+array[i], sum2, diff);
s1.pop_back();
}
if((s2.size()<=N/2 && N%2==1) || (s2.size()<N/2 && N%2==0)) { //odd length array
s2.push_back(array[i]);
findTwoSubset(array,s1, s2, solution_s1, solution_s2, i+1, sum1, sum2+array[i], diff);
s2.pop_back();
}
}
}
void findTwoSubset(const vector<int>&array,vector<int>& solution_s1, vector<int>& solution_s2) {
vector<int> s1, s2;
int diff=INT_MAX;
findTwoSubset(array, s1, s2, solution_s1, solution_s2, 0, 0,0, diff);
}
int main() {
vector<int> array={1,2,3,6,7,8,9};
vector<int> s1;
vector<int> s2;
findTwoSubset(array, s1, s2);
for(int i=0; i<s1.size(); ++i)
cout<<s1[i] << " ";
cout << endl;
for(int i=0; i<s2.size(); ++i)
cout<<s2[i] << " ";
cout << endl;
return 0;
}
say D(i) = arraylist with closest sum to the goal( sum(L)/2) using elements up to i th element with N elements.
then we do
D = {}
half = len(L)/2, goal = sum(L)/2
D[half - 1] = sum(L[:half])
for i in range(half, len(L)):
min_list = D[i - 1]
for j in range(0, half):
if abs(goal - sum(D.replace(j, L[i])) < abs(goal - sum(min_list)):
min_list = D.replace(j, L[i])
return D[len(L) - 1]
Basically using Dynamic Programming.
Here is my solution. It is a relaxation technique, that swaps values until we reach a minimal difference between the sums of the two split arrays. The steps are as follows:
1) Input is an array of size N.
2) Initialize the two arrays a(size n) and b(size m) by simply splitting the input array. n+m=N.
2) Create a 2D difference table of size n X m, where difference[i,j] = a[i]-b[j];
3) Compute the sums a and b, and compute the error = sum(a) - sum(b);
4) Now we do the relaxation iterations, where we swap values of a and b until the error between their sums reaches a minimum. We find the indices to swap by looking at the difference table. We want the value/indices in the difference table closest to 0.5*error. We need half because we want to increase the value of one array by 0.5*error, and decrease the value of the other by 0.5*error.
5) After swapping the values, we must update the difference table, but only have to update one row and one column, so it is fast.
6) The relaxation iterations stop when the error stops reducing.
This is O(N^3) in time theoretically, but seems to be O(N^2) in reality.
The relaxation seems to work fast.
Also O(N^2) in space, but around 0.25*N^2 space to be more accurate.
The code is in C++. Please try it and let me know if it works for you. I have tested in on random arrays of up to size 2000, and it works.
#include <iostream>
#include <iomanip>
using namespace std;
int getSum(int* a, int n)
{
int sum(0);
for(int i=0; i<n; i++)
sum += a[i];
return sum;
}
//
void getClosestDiffIndices(int val, int** diff, int n, int m, int& ii, int& jj)
{
// find the closest position of the difference array to val
ii = 0;
jj = 0;
int err = abs(val-diff[0][0]);
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
if(err > abs(val-diff[i][j]))
{
err = abs(val-diff[i][j]);
ii = i;
jj = j;
}
}
//
void fixRowCol(int** diff, int n, int m, int ii, int jj, int* a, int* b)
{
// only need to update the row ii and column jj
for(int i=0; i<n; i++)
diff[i][jj] = a[i]-b[jj];
for(int j=0; j<m; j++)
diff[ii][j] = a[ii]-b[j];
}
//
void balanceArrays(int* a, int n, int* b, int m)
{
// 2D array to hold the differences between the arrays 'a' and 'b'
int** diff = new int*[n];
for(int k=0; k<n; k++)
diff[k] = new int[m];
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
diff[i][j] = a[i]-b[j];
int sum_a = getSum(a,n);
int sum_b = getSum(b,m);
int error0 = sum_a - sum_b;
if(error0==0)
return;
for(int k=0; k<n; k++)
{
int ii,jj;
getClosestDiffIndices(0.5*error0,diff,n,m,ii,jj);
swap(a[ii],b[jj]);
sum_a = getSum(a,n);
sum_b = getSum(b,m);
int error1 = sum_a - sum_b;
if(error1==0)
{
error0 = error1;
break;
}
else if(abs(error1)>=abs(error0)) // stop when error no longer reduces
{
swap(a[ii],b[jj]); // swap back to lower error and break
break;
}
else
{
error0 = error1;
fixRowCol(diff,n,m,ii,jj,a,b); // only update row ii and col jj
}
}
for(int k=0; k<n; k++)
delete []diff[k];
delete []diff;
}
//
void getSplitArrays(int* InitialArray, int N, int*& a, int& n, int*& b, int& m)
{
// first arbitrarily split the large array into two of same
// size, or only differene in size by one
n = N/2;
m = N/2;
if(N%2==1)
n++;
a = new int[n];
b = new int[m];
int k=0;
for(int i=0; i<n; i++)
a[i] = InitialArray[k++];
for(int i=0; i<m; i++)
b[i] = InitialArray[k++];
balanceArrays(a,n,b,m);
}
//
int main()
{
int N = 1000;
int* InitialArray = new int[N]; // test array with random values
int range = 100;
for(int i=0; i<N; i++)
InitialArray[i] = rand()%range;
int *a, *b;
int n,m;
getSplitArrays(InitialArray,N, a,n, b,m);
cout << "Array 1 size: " << n << ", sum = " << getSum(a,n) << endl;
cout << "Array 2 size: " << m << ", sum = " << getSum(b,m) << endl;
delete[] a;
delete[] b;
delete[] InitialArray;
}
Dynamic programming based approach.
Maintain a matrix DP[0..n+1][0..sum+1]
where DP[i][j] = 1 if there is a subset in A[0...i-1] whose sum is equal to j
Recurrence equation
DP[i][j] = 1 if DP[i-1][j] == 1 // if the sum j is possible in A[0..i-1]
or if DP[i-1][j-A[i]] == 1 // if sum j-A[i] is possible in A[0..i-1]
Base case
DP[0..n][0] = 1 // sum zero is always possible
public static void findSubsets(int []a) {
int [][] dp = new int [a.length+1][1000]; // assume max sum is 1000
int sum = 0;
for(int i=0; i<a.length; i++) sum += a[i];
for(int i=0; i<a.length+1; i++) dp[i][0] = 1; // sum zero is always possible
for(int i=1; i<=a.length; i++) {
for(int s=1; s<=sum; s++) {
if(s >= a[i-1])
// add or skip current item
dp[i][s] = Math.max(dp[i-1][s], dp[i-1][s-a[i-1]]);
// otherwise check if this was possible in a[0..i-1] subarray
else dp[i][s] = dp[i-1][s];
}
}
int halfSum = sum/2;
int partition1 = 0;
for(int s=halfSum; s>=0; s--) {
if(dp[a.length][s] == 1) { // if sum s is possible in the array
partition1 = s;
break;
}
}
int partition2 = sum - partition1;
System.out.println("Two partitions: sum1: " + partition1 + ", sum2: " + partition2);
}
Above solution will work but it won't split the partitions in equal numbers. To achieve that we need to keep track of counts of the elements in subsets as well.
So the new equation will be --
Maintain a matrix DP[0..n+1][0..sum+1][0...n+1]
where DP[i][j][n] = 1 if there is a subset in A[0...i-1] whose sum is equal to j WITH COUNT n is possible
Recurrence equation
DP[i][j][n] = 1 if DP[i-1][j][n] == 1 // if the sum j is possible in A[0..i-1] with count n
or if DP[i-1][j-A[i]][n-1] == 1 // if sum j-A[i] is possible in A[0..i-1] with count n-1
Base case
DP[0..n][0][0] = 1 // sum zero with count 0 is always possible
Working code:
public static void findSubsets(int [] a) {
// array length is not even, we can't partition that in equal partitions
if(a.length%2 != 0) {
System.out.println("Balanced partition not possible.");
return;
}
int sum = 0;
for(int i=0; i<a.length; i++) sum += a[i];
int [][][] dp = new int[a.length+1][sum+1][a.length+1];
// sum zero with zero elements is always possible
for(int i=0; i<=a.length; i++) dp[i][0][0] = 1;
for(int i=1; i<=a.length; i++) {
for(int s=1; s<=sum; s++) {
for(int n=1; n<=a.length; n++) {
if(s >= a[i-1])
dp[i][s][n] = Math.max(dp[i-1][s][n],
dp[i-1][s-a[i-1]][n-1]);
else
dp[i][s][n] = dp[i-1][s][n];
}
}
}
int halfSum = sum/2;
int halfCount = a.length/2;
int partition1=0, partition2=0;
for(int s=halfSum; s>=0; s--) {
if(dp[a.length][s][halfCount] == 1) {
partition1 = s;
break;
}
}
partition2 = sum - partition1;
System.out.println(
"Partition found with " + a.length / 2
+ " elements: sum1: "
+ partition1
+ ", sum2: " + partition2);
}
Above solution will work for finding partitions with sum S and with any number of elements.
Hope this helps.
Ignore my previous solution, that's incomplete. I'm trying to edit that, but it's not working.
Dynamic programming based approach.
Maintain a matrix DP[0..n+1][0..sum+1]
where DP[i][j] = 1 if there is a subset in A[0...i-1] whose sum is equal to j
Recurrence equation
DP[i][j] = 1 if DP[i-1][j] == 1 // if the sum j is possible in A[0..i-1]
or if DP[i-1][j-A[i]] == 1 // if sum j-A[i] is possible in A[0..i-1]
Base case
DP[0..n][0] = 1 // sum zero is always possible
public static void findSubsets(int []a) {
int [][] dp = new int [a.length+1][1000]; // assume max sum is 1000
int sum = 0;
for(int i=0; i<a.length; i++) sum += a[i];
for(int i=0; i<a.length+1; i++) dp[i][0] = 1; // sum zero is always possible
for(int i=1; i<=a.length; i++) {
for(int s=1; s<=sum; s++) {
if(s >= a[i-1])
dp[i][s] = Math.max(dp[i-1][s], dp[i-1][s-a[i-1]]); // add or skip current item
else dp[i][s] = dp[i-1][s]; // otherwise check if this was possible in a[0..i-1] subarray
}
}
int halfSum = sum/2;
int partition1 = 0;
for(int s=halfSum; s>=0; s--) {
if(dp[a.length][s] == 1) { // if sum s is possible in the array
partition1 = s;
break;
}
}
int partition2 = sum - partition1;
System.out.println("Two partitions: sum1: " + partition1 + ", sum2: " + partition2);
}
Above solution will work but it won't split the partitions in equal numbers. To achieve that we need to keep track of counts of the elements in subsets as well.
So the new equation will be --
Maintain a matrix DP[0..n+1][0..sum+1][0...n+1]
where DP[i][j][n] = 1 if there is a subset in A[0...i-1] whose sum is equal to j WITH COUNT n is possible
Recurrence equation
DP[i][j][n] = 1 if DP[i-1][j][n] == 1 // if the sum j is possible in A[0..i-1] with count n
or if DP[i-1][j-A[i]][n-1] == 1 // if sum j-A[i] is possible in A[0..i-1] with count n-1
Base case
DP[0..n][0][0] = 1 // sum zero with count 0 is always possible
Working code:
public static void findSubsets(int [] a) {
// array length is not even, we can't partition that in equal partitions
if(a.length%2 != 0) {
System.out.println("Balanced partition not possible.");
return;
}
int sum = 0;
for(int i=0; i<a.length; i++) sum += a[i];
int [][][] dp = new int[a.length+1][sum+1][a.length+1];
// sum zero with zero elements is always possible
for(int i=0; i<=a.length; i++) dp[i][0][0] = 1;
for(int i=1; i<=a.length; i++) {
for(int s=1; s<=sum; s++) {
for(int n=1; n<=a.length; n++) {
if(s >= a[i-1])
dp[i][s][n] = Math.max(dp[i-1][s][n], dp[i-1][s-a[i-1]][n-1]);
else
dp[i][s][n] = dp[i-1][s][n];
}
}
}
int halfSum = sum/2;
int halfCount = a.length/2;
int partition1=0, partition2=0;
for(int s=halfSum; s>=0; s--) {
if(dp[a.length][s][halfCount] == 1) {
partition1 = s;
break;
}
}
partition2 = sum - partition1;
System.out.println(
"Partition found with " + a.length / 2
+ " elements: sum1: "
+ partition1
+ ", sum2: " + partition2);
}
Above solution will work for finding partitions with sum S and with any number of elements.
Hope this helps.
Loop through all the elements but maintain 2 containers and 2 variables called sum1 and sum2. Take one element from the initial collection assign to one containers and increment the sum for it. Now pick the next element and to other container and increment its sum.
Now for all the remaining elements perform the following check: add the next element to the container with smaller magnitude of 'sum' variable.
In the end the we will have 2 containers with possiblly unequal number of element.
Find the number elements that need to be removed from one and added to another.
Select smallest possible values and put them in the other container.
keeps adding to one left side until equal or left side is greater then adds to right side till it equals left
//returns index of start of right half
public static int half(int[] a){
int left_sum =0, right_sum=0, right =a.length;
for(int i =a.length-1; i>=0;i--){
if(right_sum <= left_sum){
right_sum += a[i];
swap(a, i, --right);
}else{
left_sum += a[i];
}
}
return right;
}
public static void swap(int[] a , int i, int k){
int temp = a[i];
a[i] = a[k];
a[k] = temp;
}
#include<stdio.h>
void main()
{
int n,n1,n2;
printf("\n\tEnter array size:");
scanf("%d",&n);
if(n%2==0)
n1=n2=n/2;
else
{
n1=n2=n/2;
n1+=1;
}
int i,j,arr[n],arr1[n1],arr2[n2],max,pos,turn=0,x=0,y=0,flag=0,flag1=0;
printf("\n\tEnter array elements : ");
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
max=-1;
j=n;
while(j>0)
{
for(i=0;i<n;i++)
if(arr[i]>max)
{
pos=i;
max=arr[i];
}
arr[pos]=-1;
if(flag1==0)
{
arr1[x++]=max;
flag1=1;
}
else
{
if(flag==0)
{
if(turn%2!=0)
flag=1;
arr2[y++]=max;
}
else
{
if(turn%2==0)
flag=0;
arr1[x++]=max;
}
turn++;
}
j--;
max=-1;
}
printf("\n\tarray1 : ");
for(i=0;i<x;i++)
printf("%d ",arr1[i]);
printf("\n\tarray2 : ");
for(i=0;i<y;i++)
printf("%d ",arr2[i]);
printf("\n");
int add1=0,add2=0;
for(i=0;i<x;i++)
add1+=arr1[i];
for(i=0;i<y;i++)
add2+=arr2[i];
printf("\n\tarray1 sum : %d",add1);
printf("\n\tarray2 sum : %d\n",add2);
}
#include<stdio.h>
void main()
{
int n,n1,n2;
printf("\n\tEnter array size:");
scanf("%d",&n);
if(n%2==0)
n1=n2=n/2;
else
{
n1=n2=n/2;
n1+=1;
}
int i,j,arr[n],arr1[n1],arr2[n2],max,pos,turn=0,x=0,y=0,flag=0,flag1=0;
printf("\n\tEnter array elements : ");
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
max=-1;
j=n;
while(j>0)
{
for(i=0;i<n;i++)
if(arr[i]>max)
{
pos=i;
max=arr[i];
}
arr[pos]=-1;
if(flag1==0)
{
arr1[x++]=max;
flag1=1;
}
else
{
if(flag==0)
{
if(turn%2!=0)
flag=1;
arr2[y++]=max;
}
else
{
if(turn%2==0)
flag=0;
arr1[x++]=max;
}
turn++;
}
j--;
max=-1;
}
printf("\n\tarray1 : ");
for(i=0;i<x;i++)
printf("%d ",arr1[i]);
printf("\n\tarray2 : ");
for(i=0;i<y;i++)
printf("%d ",arr2[i]);
printf("\n");
int add1=0,add2=0;
for(i=0;i<x;i++)
add1+=arr1[i];
for(i=0;i<y;i++)
add2+=arr2[i];
printf("\n\tarray1 sum : %d",add1);
printf("\n\tarray2 sum : %d\n",add2);
}
#include<stdio.h>
void main()
{
int n,n1,n2;
printf("\n\tEnter array size:");
scanf("%d",&n);
if(n%2==0)
n1=n2=n/2;
else
{
n1=n2=n/2;
n1+=1;
}
int i,j,arr[n],arr1[n1],arr2[n2],max,pos,turn=0,x=0,y=0,flag=0,flag1=0;
printf("\n\tEnter array elements : ");
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
max=-1;
j=n;
while(j>0)
{
for(i=0;i<n;i++)
if(arr[i]>max)
{
pos=i;
max=arr[i];
}
arr[pos]=-1;
if(flag1==0)
{
arr1[x++]=max;
flag1=1;
}
else
{
if(flag==0)
{
if(turn%2!=0)
flag=1;
arr2[y++]=max;
}
else
{
if(turn%2==0)
flag=0;
arr1[x++]=max;
}
turn++;
}
j--;
max=-1;
}
printf("\n\tarray1 : ");
for(i=0;i<x;i++)
printf("%d ",arr1[i]);
printf("\n\tarray2 : ");
for(i=0;i<y;i++)
printf("%d ",arr2[i]);
printf("\n");
int add1=0,add2=0;
for(i=0;i<x;i++)
add1+=arr1[i];
for(i=0;i<y;i++)
add2+=arr2[i];
printf("\n\tarray1 sum : %d",add1);
printf("\n\tarray2 sum : %d\n",add2);
}
It is an optimization problem:
- Objective function: Min(lambda1*X1+lamda2*X2 + ... + lamdaN*XN)
- Where lamda(i) either equal to 0 or 1
and Sigma(lamda(i)) = m, m is N/2
void TestCases
{
DataArray result;
// solution: 1, 8, 9
assert(DivideToTwoPartsWithEqualSum(DataArray{ 1, 2, 3, 6, 8, 9, 7 }, result) == 18.0);
// solution: 5, 7, 62
assert(DivideToTwoPartsWithEqualSum(DataArray{ 5, 7, 50, 8, 9, 62 }, result) == 74);
// solution: 10, 20
assert(DivideToTwoPartsWithEqualSum(DataArray{ 1, 10, 11, 18, 20 }, result) == 30);
// solution: 1, 10, 13
assert(DivideToTwoPartsWithEqualSum(DataArray{ 1, 7, 8, 9, 10, 13 }, result) == 24);
}
Please refer C++ code to cpluspluslearning-petert.blogspot.co.uk/2015/09/functional-programming-divide-array.html
If I were the interviewer asking this problem, the ideal answer I'd expect is following:
This program is similar to subset-sum and the difference that set size is fixed k=N/2. It appears that finding a set of size k summing to a given target to be "easier" than subset-sum, but this problem is still NP complete.
Proof by contradiction.
Suppose there's a P algorithm to solve this problem. If this is a case then we can use this algorithm to solve a subset-sum by finding k subsets of sizes 1,2...k and find the one which is closest. Note, that repeating the P algorithm k times yields P algorithm, so we have a P algorithm to solve subset-sum. Contradiction.
Conclusion: k-subset-sum is as "hard" as subset-sum.
That said, we can run solve this problem by doing brute force (for small Ns) and/or using approximated/heuristic methods. I can propose few ideas:
1) Time constrained brute-force with printing best solution found
2) Applying aggressive pruning - it is possible if numbers are positive
3) Applying dynamic programming and/or memoization if numbers are integers and if range of possible sums allows that
4) Relaxation Technic (already proposed) and other forms or gradient descent method.
5) Randomized swap with reporting of best result found and using simulated annealing technic to escape local optimas
6) Various fast O(Nlogn) heuristic/greedy algorithms based on pre-sorting
Like others say, this is NP-complete. This is a greedy (suboptimal) solution based on sorting. It walks backwards through the sorted array (max to min). Time is O(n*log(n)) and space is O(n). It will work for [1,2,3,6,7,8,9]
public static ArrayList[] minPartitionDifference(int[] array) {
Arrays.sort(array);
int max = (array.length + 1) / 2;
int sumA = 0, sumB = 0;
ArrayList<Integer> A = new ArrayList<>(), B = new ArrayList<>();
for (int i = array.length - 1; i >= 0; i--) {
boolean addA = (B.size() == max) || ((A.size() != max) && Math.abs(sumA + array[i] - sumB) < Math.abs(sumA - array[i] - sumB));
if (addA) {
sumA += array[i];
A.add(array[i]);
} else {
sumB += array[i];
B.add(array[i]);
}
}
System.out.println("Difference is: " + Math.abs(sumA - sumB));
System.out.println("set one: " + A);
System.out.println("set two: " + B);
return new ArrayList[] { A, B };
}
Maybe we use DP to solve it.
char dp[MAX][MAX][MAX];
vector<int> partition(const vector<int> &a) {
int n = a.size();
if (n < 2)
return a;
int m = n >> 1;
int sum = 0;
for (int x : a)
sum += x;
sum >>= 1;
dp[0][0][0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= i && j <= m; ++j) {
for (int k = 1; k <= sum; ++k) {
if (dp[i - 1][j][k] > 0)
dp[i][j][k] = 1;
else if (dp[i - 1][j - 1][k] > 0)
dp[i][j][k] = 2;
else
dp[i][j][k] = 0;
}
}
}
vector<int> ans;
while (dp[n][m][sum] == 0)
--sum;
int val = dp[n][m][sum];
while (val > 0) {
if (val == 2) {
ans.push_back(a[n - 1]);
sum -= a[n - 1];
val = dp[--n][--m][sum];
}
else {
val = dp[--n][m][sum];
}
}
return move(ans);
}
This is another DP algo in Java. I think TC is O(n*n!) and SC O(n!). It is not better than the brutal force algo of exhausting the combinations satisfying the length constraint.
public class GG_SubsetSum {
class Comb {
ArrayList<Integer> left; // keep left.size()>=right.size()
ArrayList<Integer> right;
Comb(ArrayList<Integer> left, ArrayList<Integer> right)
{
this.left = left;
this.right = right;
}
}
ArrayList<ArrayList<Integer>> partition(int[] nums)
{
ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
if(nums == null || nums.length == 0)
return ret;
ArrayList<Comb> d = new ArrayList<>();
ArrayList<Integer> d0 = new ArrayList<>();
d0.add(nums[0]);
d.add(new Comb(d0, new ArrayList<>()));
for(int i=1; i< nums.length; ++i) {
ArrayList<Comb> newCombs = new ArrayList<>();
for(int j=0; j<d.size(); ++j) {
Comb c = d.get(j);
int lengthDiff = c.left.size() - c.right.size();
if(lengthDiff == 0) {
Comb c1 = new Comb((ArrayList<Integer>)c.left.clone(), (ArrayList<Integer>)c.right.clone());
c1.right.add(nums[i]); // right will be longer
newCombs.add(new Comb(c1.right, c1.left)); // create a new Comb to keep left longer.
c.left.add(nums[i]);
} else if(lengthDiff == 1) {
Comb c1 = new Comb((ArrayList<Integer>)c.left.clone(), (ArrayList<Integer>)c.right.clone());
c1.right.add(nums[i]);
newCombs.add(c1);
c.left.add(nums[i]);
}
else { // lengthDiff == 2
c.right.add(nums[i]);
}
}
for(int j=0; j<newCombs.size(); ++j)
d.add(newCombs.get(j));
}
double min = Double.MAX_VALUE;
int minIndex = -1;
for(int i=0; i<d.size(); ++i) {
Comb c = d.get(i);
int lengthDiff = c.left.size() - c.right.size();
if(lengthDiff <= 1) {
int leftSum = 0;
for(int j=0; j<c.left.size(); ++j) {
leftSum += c.left.get(j);
}
int rightSum = 0;
for(int j=0; j<c.right.size(); ++j) {
rightSum += c.right.get(j);
}
int lmin = Math.abs(leftSum - rightSum);
if(lmin < min) {
min = lmin;
minIndex = i;
}
}
}
ret.add(d.get(minIndex).left);
ret.add(d.get(minIndex).right);
return ret;
}
}
private static int partition(ArrayList<Integer> array, int sum)
{
// Print a, b and return difference
ArrayList<Integer> a = new ArrayList<Integer>();
ArrayList<Integer> b = new ArrayList<Integer>();
int half = sum/2, aSum=0, bSum=0;
int count = array.size()-1;
int i = 0, j = count;
while(j >= 0)
{
while( (aSum <= bSum) && (j >= 0))
{
aSum = aSum + array.get(j);
a.add( array.get(j));
j--;
}
while( (bSum <= aSum) && (j >= 0))
{
bSum = bSum + array.get(j);
b.add( array.get(j));
j--;
}
}
System.out.println(a);
System.out.println(b);
return Math.abs(bSum - aSum);
}
/*** Splitting Array ***/
#include <stdio.h>
#define ARRAY_SZ 9
int array[ARRAY_SZ] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
void merge(int left, int right, int mid) {
int i = left, j = mid+1, k = left;
int temp[ARRAY_SZ] = { 0 };
while((i <= mid) && (j <= right)) {
if(array[i] < array[j]) {
temp[k] = array[j];
j++;
} else {
temp[k] = array[i];
i++;
}
k++;
}
while (i <= mid) {
temp[k] = array[i];
i++;
k++;
}
while (j <= right) {
temp[k] = array[j];
j++;
k++;
}
for(i = left;i < k;i++) {
array[i] = temp[i];
}
}
void mergeSort(int left, int right) {
int mid = (left+right) / 2;
if (left < right) {
mergeSort(left, mid);
mergeSort(mid+1, right);
merge(left, right, mid);
}
}
int main() {
int i = 0, j = 0, sum_arr1 = 0, sum_arr2 = 0;
int k = 0;
int arr1[((ARRAY_SZ) / 2)] = { 0 };
int arr2[(ARRAY_SZ) - ((ARRAY_SZ) / 2)] = { 0 };
mergeSort(0, ARRAY_SZ-1);
int arr1_sz = ((ARRAY_SZ) / 2);
int arr2_sz = (ARRAY_SZ) - ((ARRAY_SZ) / 2);
arr1[0] = array[0];
sum_arr1 = arr1[0];
i = 1; k = 1;
while((i < arr1_sz) && (j < arr2_sz)) {
if(sum_arr1 > sum_arr2) {
arr2[j] = array[k];
sum_arr2 += arr2[j];
j++;
} else {
arr1[i] = array[k];
sum_arr1 += arr1[i];
i++;
}
k++;
}
while (i < arr1_sz) {
arr1[i] = array[k];
k++;
i++;
}
while (j < arr2_sz) {
arr2[j] = array[k];
k++;
j++;
}
printf("\n");
for(i = 0;i < ARRAY_SZ;i++) {
printf("%d ",array[i]);
}
printf("\n");
for(i = 0;i < arr1_sz;i++) {
printf("%d ",arr1[i]);
}
printf("\n");
for(i = 0;i < arr2_sz;i++) {
printf("%d ",arr2[i]);
}
printf("\n");
}
#include<iostream>
#include <math.h>
#include<vector>
#include<algorithm>
using namespace std;
int sum(vector<int> &vec) {
int sum_ = 0;
for(vector<int>::iterator iter = vec.begin(); iter != vec.end(); iter++) {
sum_ += *iter;
}
return sum_;
}
void divide_min_diff(vector<int> *arr) {
sort(arr->begin(), arr->end());
int x = arr->size() / 2;
vector<int> first(arr->begin(), arr->begin() + x);
vector<int> second(arr->begin() + x, arr->end());
vector<int>::reverse_iterator riter;
vector<int>::iterator iter;
iter = first.begin();
riter = second.rbegin();
while (iter != first.end() && riter != second.rend()) {
int diff = sum(second) - sum(first);
if ((*riter - *iter) < diff) {
iter_swap(iter, riter);
}
iter++;
riter++;
}
for (std::vector<int>::const_iterator i = first.begin(); i != first.end(); ++i)
std::cout << *i << ' ';
cout << "Second" << endl;
for (std::vector<int>::const_iterator i = second.begin(); i != second.end(); ++i)
std::cout << *i << ' ';
}
int main(void) {
vector<int> arr;
arr.push_back(1);
arr.push_back(2);
arr.push_back(9);
arr.push_back(7);
arr.push_back(6);
arr.push_back(3);
arr.push_back(8);
divide_min_diff(&arr);
getchar();
return 1;
}
Complexity: Time: O(nlogn), Space: O(1)
def partition(A):
A.sort()
for i in range(1, len(A)/2, 2):
A[i], A[-1-(i - 1)] = A[-1 - (i - 1)], A[i]
if len(A) % 2 and sum(A[0:len(A)/2]) < sum(A[len(A)/2 + 1:]):
return A[:len(A)/2 + 1], A[len(A)/2 + 1:]
else:
return A[:len(A)/2], A[len(A)/2:]
Here is my O(n^2) time and O(n) space using a greedy approach - that is it will return a suboptimal solution.
Idea is to partition the array in pairs of element that would distribute the sum as uniformly as possible across the partitions. So, each time we would try to take 2 pairs and put one pair in a partition and the other pair in the other partition.
1. Sort the array
2. If number of elements in less than 4 then create partitions accordingly for each cases when we have 1 element or 2 element or 3 element in the array.
3. Otherwise we will take 2 pair each time and put into two partition such that it minimizes the sum diff.
4. Pick the pair(largest, smallest) elemets in the the sorted array and put it to the smaller (wr.to sum) partition.
5. Then pick the second largest element and find its buddy to put them in the 'other' partition such that sum of second largest and its buddy minimizes the sum difference of the partitions.
6. The above approach will give a suboptimal solution. The problem in NP complete so, we can't have an optimal solution but we can improve the approximation ratio as follows.
7. If we have suboptimal solution (ie. sum diff != 0) then we try to improve the solution by swapping a large element in the larger partition with a small element in the smaller partition such that the swap actually minimizes the sum diff.
- zahidbuet106 September 07, 2015