Google Interview Question for Software Engineers


Country: United States




Comment hidden because of low score. Click to expand.
1
of 3 vote

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.

//overall O(n^2) time and O(n) space solution using a greedy approach
	public static ArrayList<Integer>[] findEqualPartitionMinSumDif(int A[]){
		//first sort the array - O(nlgn)
		Arrays.sort(A);
		ArrayList<Integer> partition1 = new ArrayList<Integer>();
		ArrayList<Integer> partition2 = new ArrayList<Integer>();
		
		//create index table to manage largest unused and smallest unused items
		//O(n) space and O(nlgn) time to build and query the set
		TreeSet<Integer> unused = new TreeSet<>();
		for(int i = 0; i<A.length; i++){
			unused.add(i);
		}
		
		int i = 0;
		int j = A.length-1;
		int part1Sum = 0;
		int part2Sum = 0;
		int diffSum = 0;
		
		//O(n^2) processing time
		while(unused.size() > 0){
			i = unused.first();
			j = unused.last();
			diffSum = part1Sum-part2Sum;
			
			//in case of size of the array is not multiple of 4 then we need to process last 3(or 2 or 1)
			//element to assign partition. This is special case handling
			if(unused.size() < 4){
				switch(unused.size()){
					case 1: 
						//put the 1 remaining item into smaller partition
						if(diffSum > 0){
							partition2.add(A[i]);
							part2Sum += A[i];
						}
						else{
							partition1.add(A[i]);
							part1Sum += A[i];
						}
					break;
					case 2:
						//among the remaining 2 put the max in smaller and min in larger bucket
						int max = Math.max(A[i], A[j]);
						int min = Math.min(A[i], A[j]);
						if(diffSum > 0){
							partition2.add(max);
							partition1.add(min);
							part2Sum += max;
							part1Sum += min;
						}
						else{
							partition1.add(max);
							partition2.add(min);
							part1Sum += max;
							part2Sum += min;
						}
					break;
					case 3:
						//among the remaining 3 put the two having total value greater then the third one into smaller partition
						//and the 3rd one to larger bucket 
						unused.remove(i);
						unused.remove(j);
						int middle = unused.first();
						
						if(diffSum > 0){
							if(A[i]+A[middle] > A[j]){
								partition2.add(A[i]);
								partition2.add(A[middle]);
								partition1.add(A[j]);
								part2Sum += A[i]+A[middle];
								part1Sum += A[j];
							}
							else{
								partition2.add(A[j]);
								partition1.add(A[i]);
								partition1.add(A[middle]);
								part1Sum += A[i]+A[middle];
								part2Sum += A[j];
							}
						}
						else{
							if(A[i]+A[middle] > A[j]){
								partition1.add(A[i]);
								partition1.add(A[middle]);
								partition2.add(A[j]);
								part1Sum += A[i]+A[middle];
								part2Sum += A[j];
							}
							else{
								partition1.add(A[j]);
								partition2.add(A[i]);
								partition2.add(A[middle]);
								part2Sum += A[i]+A[middle];
								part1Sum += A[j];
							}
						}
					break;
					default:
				}
				
				diffSum = part1Sum-part2Sum;
				break;
			}
			
			//first take the largest and the smallest element to create a pair to be inserted into a partition
			//we do this for having a balanced distribute of the numbers in the partitions
			//add pair (i, j) to the smaller partition 
			int pairSum = A[i]+A[j];
			int partition = diffSum > 0 ? 2 : 1;
			if(partition == 1){
				partition1.add(A[i]);
				partition1.add(A[j]);
				part1Sum += pairSum;
			}
			else{
				partition2.add(A[i]);
				partition2.add(A[j]);
				part2Sum += pairSum;
			}
			
			//update diff
			diffSum = part1Sum-part2Sum;
			//we have used pair (i, j)
			unused.remove(i);
			unused.remove(j);
			//move j to next big element to the left
			j = unused.last();
			//now find the buddy for j to be paired with such that sum of them is as close as to pairSum
			//so we will find such buddy A[k], i<=k<j such that value of ((A[j]+A[k])-pairSum) is minimized.
			int buddyIndex = unused.first();
			int minPairSumDiff = Integer.MAX_VALUE;
			for(int k = buddyIndex; k<j; k++){
				if(!unused.contains(k))
					continue;
				
				int compPairSum = A[j]+A[k];
				int pairSumDiff = Math.abs(pairSum-compPairSum);
				
				if(pairSumDiff < minPairSumDiff){
					minPairSumDiff = pairSumDiff;
					buddyIndex = k;
				}
			}
			
			//we now find buddy for j. So we add pair (j,buddyIndex) to the other partition
			if(j != buddyIndex){
				pairSum = A[j]+A[buddyIndex];
				if(partition == 2){
					partition1.add(A[j]);
					partition1.add(A[buddyIndex]);
					part1Sum += pairSum;
				}
				else{
					partition2.add(A[j]);
					partition2.add(A[buddyIndex]);
					part2Sum += pairSum;
				}
				
				//we have used pair (j, buddyIndex)
				unused.remove(j);
				unused.remove(buddyIndex);
			}
		}
		
		//if diffsum is greater than zero then we can further try to optimize by swapping 
		//a larger elements in large partition with an small element in smaller partition
		//O(n^2) operation with O(n) space
		if(diffSum != 0){
			Collections.sort(partition1);
			Collections.sort(partition2);
			
			diffSum = part1Sum-part2Sum;
			ArrayList<Integer> largerPartition = (diffSum > 0) ? partition1 : partition2;
			ArrayList<Integer> smallerPartition = (diffSum > 0) ? partition2 : partition1;
			
			int prevDiff = Math.abs(diffSum);
			int largePartitonSwapCandidate = -1;
			int smallPartitonSwapCandidate = -1;
			//find one of the largest element from large partition and smallest from the smaller partition to swap 
			//such that it overall sum difference in the partitions are minmized
			for(i = 0; i < smallerPartition.size(); i++){
				for(j = largerPartition.size()-1; j>=0; j--){
					int largerVal = largerPartition.get(j);
					int smallerVal = smallerPartition.get(i);
					
					//no point of swapping larger value from smaller partition
					if(largerVal <= smallerVal){
						continue;
					}

					//new difference if we had swapped these elements
					int diff = Math.abs(prevDiff - 2*Math.abs(largerVal - smallerVal));
					if(diff == 0){
						largerPartition.set(j, smallerVal);
						smallerPartition.set(i, largerVal);
						return new ArrayList[]{largerPartition, smallerPartition};
					}
					//find the pair to swap that minimizes the sum diff
					else if (diff < prevDiff){
						prevDiff = diff;
						largePartitonSwapCandidate = j;
						smallPartitonSwapCandidate = i;
					}
				}
			}
			
			//if we indeed found one such a pair then swap it. 
			if(largePartitonSwapCandidate >=0 && smallPartitonSwapCandidate >=0){
				int largerVal = largerPartition.get(largePartitonSwapCandidate);
				int smallerVal = smallerPartition.get(smallPartitonSwapCandidate);
				largerPartition.set(largePartitonSwapCandidate, smallerVal);
				smallerPartition.set(smallPartitonSwapCandidate, largerVal);
				return new ArrayList[]{largerPartition, smallerPartition};
			}
		}
		
		return new ArrayList[]{partition1, partition2};
	}

- zahidbuet106 September 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

good solution. Does it return minimum difference partition always? or is it a greedy that is returning suboptimal solutions only?

- dhs.du.08 September 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Weiqiang August 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- Ravi Peri August 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Few lines explaining the logic before pasting the code would be great!!

- infinity August 26, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Ravi Peri August 26, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

- hp August 26, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Probably, you need to re-sort the sub-arrays, or scan through the sub-arrays to find the swap pair.

- guangsumengmianxia August 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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)

- Anonymous August 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

yeah, he is right, this algorithm is flawed, can someone give some idea how to correct it?

- jigili August 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
    }

}

- Arpit October 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;

}

- Anonymous August 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Try with {1, 24, 9,7 ,6,44,8};
getting wrong answer

- infinity August 26, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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}

- Anch August 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Don't you think, it should be
SetA- [5, 62, 8],
SetB - [7, 50, 9]
P.S. :- See my soln

- infinity August 26, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

It should be [50,8,9] (sum: 67) and [5,7,62] (sum: 74) -- Correct solution via Dynamic Programming.

- Diego August 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- estjang August 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

if n < 20 is bit mask.

sum = a1+a2+ ..... + an
if 00010101 is val = a4+a6+a8 another value is sum - val Now mn = min(mn, diff(sum-val,val))
and answer is mn
Solution o(2^n).

- adiya.tb August 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
     }
}

- infinity August 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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:]

- Mr. Anonymous August 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Wrong answer. print partition([1,10, 11, 18, 20]) you get ([1, 20, 11], [18, 10]), which should be [1, 18, 11], [20, 10]

- Anonymous August 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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:]

- Mr. Anonymous August 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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:]

- Random August 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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:]

- YOLO August 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(nlogn) time and O(1) space.

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:]

- Anonymous August 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

Its subset sum problem. Have to find elements of the arrays that can sum to N/2 where N is sum of all elements in array.

- Harsha August 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(nlogn) time and O(1) space

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:]

- Anonymous August 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- harshavardhanab August 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You've already said this, logged in as Harsha.

- ddascalescu September 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Vinay August 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Consider this case {1, 7, 8, 9, 10, 13}
Set A = {7, 8, 9}
Set B = {1, 10, 13}

- brianw August 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*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:");
	}
}

- Andy August 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*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:");
}
}

- cxy0224 August 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

we can apply subset sum problem staritge here with sum=sum/2 when array contain even number of elements and sum=sum of all elements except smallest /2 +smallest element

- pbox August 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I believe we can find all subsets of N/2 elements, then find the sum and sum of the rest of elements and then keep the minimum

- jigili August 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

calculate total sum of elements and let it be sum.
generate all subsets and calcutate subset sum
sum1=subset sum
sum2=sum-subset sum;
diff=sum1 difference sum2;
if(diff<min)
min=diff;

complexity:O(2^n) since there are total 2^n subsets.

- ram August 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- jigili August 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- jigili August 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- jigili August 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- kevin k August 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This problem is NP Complete

- 王爷爷 August 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- pthiyana August 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- HauntedGhost August 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- HauntedGhost August 31, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- amitsriv9 September 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}

- ghost September 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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);
}

- akash September 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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);	
}

- akash September 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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);
}

- akash September 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 4 vote

This is a special case of subset sum problem, called 'The Easiest Hard Problem' where, for a given set {x1, x2, ..., xn} that sums to S, you will find a subset of size n/2 (or n/2+1) that sums to S/2 (or S/2+1).

- zahidbuet106 September 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- peter tang September 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- 0xF4 September 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 };
        }

- louis September 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

- malinbupt September 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Best solution so far but has a couple of bugs.

- R* October 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Best solution so far, only it has a couple of bugs.

- rst October 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
    }
}

- jiangok2006 November 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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);
}

- Rakesh September 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

/*** 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");
	
}

- imbalajiravindran September 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

#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;
}

- Ravi Peri August 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

your code does not work, for the test case you have tested, the solution should be 9,8,1, and 6,7,2,3, but your code's results are not the same

- jigili August 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
-2
of 4 vote

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:]

- 2BitFlipFlop August 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Very elegant solution.

- Jacob August 26, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Unfortunately, this solution does not work. For input: [1,2,3,6,7,8,9] it returns ([1, 9, 3, 6], [7, 8, 2]). This solution has a difference of 19 - 17 = 2, however ([1,8,9],[2,3,6,7]) would be a better solution with the difference 18 - 18 = 0.

- Siretu August 29, 2015 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More