Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
Here is an implementation in Java of Miguel Oliveira's ideas.
public class DivideArrayAverage2 {
// Hash map of sum -> subset
HashMap<Key, int[]> map;
// Input array
int a[];
// Indices of current subset while recursing.
int b[];
// Half the sum of a.
int halfSum;
// Half the length of a.
int halfLength;
// How many iterations the algo has run.
int iterations;
class Key {
public int s;
public int n;
@Override
public boolean equals(Object obj) {
Key key = (Key)obj;
return s == key.s && n == key.n;
}
@Override
public int hashCode() {
return (s * 33) ^ n;
}
}
// Returns a single array that is a reordering of the input array where the first half has the same average as the second half; if such an array exists.
//
// Reduce problem to finding the subset with n/2 elements that sums to sum(a)/2.
// This problem is the subset sum problem with a fixed size, so use standard way of solving subset sum problem.
// Divide the array into 2 halves A and B. Calculate the sum of every subset in A and store them in a hash map [sum -> subset].
// There are 2^(n/2) subsets of A and it requires O(n) to create each subset, so the this step is O(n*2^(n/2)).
// Iterate over every subset in B and see if there is a subset in A with the same sum and correct length.
// This step is O(2^(n/2)), so the overall complexity is O(n*2^(n/2)).
int[] divide(int a[]) {
// If there are an odd number of elements, there is no solution.
if (a.length % 2 != 0) {
return null;
}
// If the sum of the elements is odd, there is no solution.
int sum = 0;
for (int i = 0; i < a.length; ++i) {
sum += a[i];
}
if (sum % 2 != 0) {
System.out.println("divide: n=" + a.length + " iterations=1");
return null;
}
// Store some stuff in member variables to that we don't have to push it onto the stack each recursion step.
this.halfSum = sum / 2;
this.halfLength = a.length / 2;
this.iterations = 0;
this.a = a;
this.map = new HashMap<Key, int[]>();
this.b = new int[halfLength];
// Build a hash map of the sums of all subsets of the 2nd half of the input array.
populateHashMap(halfLength, 0, 0);
// Iterate over all subsets of the 1st half of the input array and look for appropriate subsets in the hash map/
int tuplet[] = findSubset(0, 0, 0);
System.out.println("divide: n=" + a.length + " iterations=" + iterations);
if (tuplet != null) {
// tuplet contains indices of the input array. Use that info to construct the output array.
return tupletToResult(tuplet, a);
}
return null;
}
// O(n*2^(n/2))
void populateHashMap(int i, int s, int n) {
++iterations;
if (i == a.length) {
if (n > 0) {
Key key = new Key();
key.s = s;
key.n = n;
int subset[] = new int[n];
System.arraycopy(b, 0, subset, 0, n);
map.put(key, subset);
iterations += n;
}
return;
}
populateHashMap(i + 1, s, n);
b[n] = i;
populateHashMap(i + 1, s + a[i], n + 1);
}
// O(2^(n/2))
int[] findSubset(int i, int s, int n) {
++iterations;
if (i == a.length / 2) {
if (s == halfSum && n == a.length / 2) {
int subset[] = new int[n];
System.arraycopy(b, 0, subset, 0, n);
return subset;
}
if (n > 0) {
Key key = new Key();
key.s = halfSum - s;
key.n = halfLength - n;
int c[] = map.get(key);
if (c != null) {
int subset[] = new int[a.length / 2];
System.arraycopy(b, 0, subset, 0, n);
System.arraycopy(c, 0, subset, n, c.length);
return subset;
}
}
return null;
}
int result[] = findSubset(i + 1, s, n);
if (result != null) {
return result;
}
b[n] = i;
return findSubset(i + 1, s + a[i], n + 1);
}
// Converts an array of indices of a into the output array.
static int [] tupletToResult(int tuplet[], int a[]) {
int half = a.length / 2;
boolean b[] = new boolean[a.length];
for (int i = 0; i < half; ++i) {
b[tuplet[i]] = true;
}
int result[] = new int[a.length];
for (int i = 0, j = 0, k = half; i < a.length; ++i) {
if (b[i]) {
result[j++] = a[i];
}
else {
result[k++] = a[i];
}
}
return result;
}
You can use bitwise operations to simplify the code. Here's my implementation:
import java.io.*;
import java.util.ArrayList;
import java.util.HashMap;
public class SubsetSum {
// Array size should not exceed 40
public static void solve(int[] v) {
int i, sum, N = v.length;
for (i = sum = 0; i < N ; i++)
sum += v[i];
if (N % 2 == 1 || sum % 2 == 1) {
System.out.println("Impossible");
return;
}
int halfLength = N / 2, halfSum = sum / 2;
ArrayList<HashMap<Integer,Integer>> hash = new ArrayList<HashMap<Integer,Integer>>();
for (i = 0 ; i <= halfLength; i++)
hash.add(new HashMap<Integer,Integer>());
int mask, numSubSets = 1 << halfLength;
// process all subsets using the first half of the array. Use bitmasks to do it.
for (mask = 0; mask < numSubSets; mask++) {
int subsetSize = 0, subsetSum = 0;
for (i = 0 ; i < halfLength; i++)
if ((mask & (1 << i)) > 0) {
// mask has bit i set to 1
subsetSum += v[i];
subsetSize++;
}
hash.get(subsetSize).put(subsetSum, mask);
}
// process the other half and check the hashmaps
for (mask = 0; mask < numSubSets; mask++) {
int subsetSize = 0, subsetSum = 0;
for (i = 0 ; i < halfLength; i++)
if ((mask & (1 << i)) > 0) {
// mask has bit i set to 1. Note that we're using the other half.
subsetSum += v[i + halfLength];
subsetSize++;
}
int remSize = halfLength - subsetSize, remSum = halfSum - subsetSum;
if (hash.get(remSize).containsKey(remSum)) {
printSolution(v, hash.get(remSize).get(remSum), mask);
return;
}
}
System.out.println("No solution");
}
static void printSolution(int[] v, int leftMask, int rightMask) {
int i, indexA=0, indexB=0, halfLength = v.length / 2;
int[] a = new int[halfLength];
int[] b = new int[halfLength];
for (i = 0 ; i < halfLength; i++) {
if ((leftMask & (1 << i)) > 0)
a[indexA++] = v[i];
else
b[indexB++] = v[i];
if ((rightMask & (1 << i)) > 0)
a[indexA++] = v[i + halfLength];
else
b[indexB++] = v[i + halfLength];
}
System.out.print("Array A: ");
for (i = 0; i < halfLength; i++)
System.out.print(a[i] + " ");
System.out.print("\nArray B: ");
for (i = 0; i < halfLength; i++)
System.out.print(b[i] + " ");
System.out.println("");
}
public static void main(String[] args) {
final int input[] = {1, 20, 20, 20, 29, 30};
solve(input);
}
}
I think this can be solved like this:
1) Average of both (n/2) blocks is same=> total is same
2) Total of both blocks = 1/2 * total of n number
=> Add up all n numbers = T
=> find (n/2) numbers which add upto T/2
=> the leftover will also add up to T/2 (obvious)
we can use a DP for the above solution.. which is like the coin & sum problems
We can't use a DP as you are thinking. The constraint that the two halves should have the same sum is only true the first time we split the array.
Let A be the array s.t. sum(A) = n
Let A1, A2 be the halves s.t. sum(A1) = sum(A2) = n/2
Let A11, A12 be any two halves of A1. It is not necessary for any such A11, A12 that sum(A11) = sum(A12)!
A DP solution might be possible, but certainly not this way!
the DP i proposed is this
a = { 1,2,3,4,5,6,7,8}
find 4 elements in a which addupto 14
so you form a DP where you keep track of how many numbers you are using and whats the addition
in above case F(1) = 1(1) => () count of numbers uses
F(2) = 2(1)
F(3) = 1,2 (2) or 3(1)
F(4) = 1,3(2)
F(5) = 1,4(2) or 2,3(2)
so you throw if the count gets more than 4 and keep moving forward
@anotherguy, i think you misunderstood his post. he's not recursively spliting the parts of the array.
This solution will work in a pseudo-polynomial time (depends on the size of the integers to have a feasible space complexity) but it is a bit tricky because you must be sure to be using only N/2 numbers to achieve T/2.
No guarantee that such a division is possible but using DP the logic would be something like this:
- calculate total sum
for i=0;i<n;i++
sum+=arr[i];
- Now maintain a Sum table/huge 1D array and set SumTbl[j] = False for all j<n
and SumTbl[0] = True
- Now the trick here is that we maintain the running sum we have so far and set SumTbl[j]=True for the running sum.
In addition to that, we need to set SumTbl[j + arr[i]] = True for all j< sum-arr[i]
So, the logic would be something like:
for (i=0; i < n; i++ ) {
for (j=sum-arr[i]; j>=0;j--) {
if (SumTbl[j] != False) {
SumTbl[ j+arr[i] ] = True;
}
}
}
return SumTbl[sum/2];
Now, we dont really need to consider j from sum to 0, we could maintain a rightmost index R (initially set to 0 and set it o min (sum/2, j+arr[i]). So the logic would be
R = 0;
for (i=0; i<n;i++) {
for (j=R; j>=0;j--) {
if (SumTbl[j] !=False) {
SumTbl[j+arr[i]] = True;
}
R = min(sum/2, R+arr[i]);
}
return SumTbl[R/2]
Right! No guarantee that it is always possible. Consider the array [1,2]. This can't be divided into two sub-arrays of size 1 whose averages are equal.
As a preliminary response, the algorithm should first output whether or not such a partitioning is possible. If yes, then can print out the partitioned elements. And as far as the algorithm is considered, modifications to the DP solution of subset sum problem should work.
I am sure it's tough one. Using subset sum problem we can say that there is a solution which exist, but generating numbers which constitutes these sub-arrays would be tough one, especially when considering no overlapping elements.
I'm confused by this solution. If I follow the solution correctly, it does not work for these simple inputs:
1,-1
1,2
Here is the implementation in Java with tests:
import org.junit.Assert;
import org.junit.Test;
public class Foo {
@Test
public void test2Positive() {
int a[] = new int[] {1,1};
Assert.assertTrue(divide(a));
}
@Test
public void test2Negative() {
int a[] = new int[] {1,-1};
Assert.assertTrue(divide(a));
}
@Test
public void test2Null() {
int a[] = {1,2};
Assert.assertNull(divide(a));
}
boolean divide(int arr[]) {
int sum = 0;
for (int i=0; i < arr.length ; i++) {
sum += arr[i];
}
boolean SumTbl[] = new boolean[1024*1024];
SumTbl[0] = true;
for (int i=0; i < arr.length; i++) {
for (int j = sum - arr[i]; j >= 0; j--) {
if (SumTbl[j] != false) {
SumTbl[j + arr[i]] = true;
}
}
}
return SumTbl[sum/2];
}
}
average equal, means sum equal.
1. iterate the array, calculate the sum of the array: Sigma
2. find a sub array with n/2 elements and the sum is Sigma/2
normally like a recusive solution for step 2, cost O((n/2)!) time.
Anyone can provide better solution?
DP solution :
1. generate dp matrix upto K such that
a) k has 2 true (means there are two pairs of subset whose sum is K
b) check if two pairs are distinct and covering all elements of main set
c) if false then repeat above two steps till k reaches a optimal sum(like totalsum/tota no of elements)
1 sort the array.
2. Create two groups by picking elements in pairs but in alternate fashion.
Assuming after sorting array is a[1]....a[n]
gr1:(a[1],a[n]) (a[3], a[n-2]) so on
gr2: (a[2], a[n-1])(a[4], a[n-3]) so on
This can be done by using the subset sum algorithm where the target sum equals the half of total sum of array elements. In addition, we need to impose a limit on the permissible length of the selected sub-array so that it is equal to the half of the total number of elements in the array. Here's the code:
#include <iostream>
#include <iomanip>
#include <vector>
using namespace std;
void PrintIndice(int* arr, int len, int target, int index, vector<int>& indices, int &count, int RequiredCount)
{
if(target == 0 && count==RequiredCount)
{
cout<<"\nLength:\t"<<count<<"\n\n";
for(int i = 0; i < indices.size(); ++i)
{
cout << setw(4) << arr[indices[i]];
arr[indices[i]]=0;
}
cout << endl;
return;
}
for(int i = index; i < len; ++i)
{
if(target>=arr[i])
{
indices.push_back(i);
count++;
PrintIndice(arr, len, target - arr[i], i + 1, indices,count, RequiredCount);
count--;
indices.pop_back();
}
}
}
void FindIndicesCombination(int* arr, int len, int target,int count, int RequiredCount)
{
for(int i = 0; i < len; ++i)
{
vector<int> indices;
indices.push_back(i);
count++;
PrintIndice(arr, len, target - arr[i], i + 1, indices,count, RequiredCount);
count--;
indices.pop_back();
}
}
int main(int argc, char* argv[])
{
int arr[] = {1,2,3,4,5,6,7,8};
static int cnt=0;
int size=sizeof(arr)/sizeof(arr[0]);
int sum=0,i;
int RequiredCount =size/2;
for(i=0;i<size;i++)
sum+=arr[i];
int target=0;
FindIndicesCombination(arr,size,sum/2,cnt, RequiredCount);
return 1;
}
1.) Calculate sum of the array
requirement can now be broken in to finding sum/2
1.) calculate a recursive approach to the sum with an auxilary array to keep a track of element as a part of the sum
2.) Of all possible combinations print the one with length =n/2 of original array.
dirty code for finding sum
find sum(int []A , int [] Ix, int sum, int T, int n)
{
if(sum>T)
return;
if(sum==T)
{
if(Ix.length ==A.length /2)
print (A,Ix,n);
return;
}
for(int i = Ix[n] :i<A.lrngth;i++)
Ix[n+1]=i
findssum(A,IX,sum+A[i],n+1);
}
I think we can use DP. While finding the numbers for n/2 array I can store the indices. Since the array which we need to make is n/2 so the sum of all elements will be S such that 2S is the sum of main array in question.
Pseudocode
FindArray(A,Sum,a) be the function where A is the main array, Sum = Sum at any state, a be n/2 array which we need to fill
void FindArray(A,Sum,a)
for i = 1 to n
Stemp = Sum - A[i]
if(Stemp == 0)
{
// Found solution for that stage
Store i int a. // Use your logic
}
else if (Stemp > 0)
{
FindArray(A,Stemp,a)
}
else
{
// Do nothing
}
I don't understand why you people are assuming only positive number. Has anyone mentioned this question is valid for only positive numbers ?? What if it contains negative numbers ?
import java.util.Stack;
public class Node {
public static void main(String[] args){
int arr[] = {1,2,3,4,5,6,7,8};
int sum = 0;
int sum1=0;
Stack<Integer> st = new Stack<Integer>();
for(int i=0;i<arr.length;i++){
sum += arr[i];
}
out:
for(int i=0;i<arr.length;i++){
sum1 = arr[i];
for(int j=i+1;j<arr.length;j++){
sum1 += arr[j];
if(sum1 == sum/2){
st.push(i);
st.push(j);
break out;
}
}
}
System.out.println(st);
}
}
O(2^n) is pretty simple. I think this problem is "NP-complete".
Model:
Solve the following integer equations over binary variables:
a_1 x_1 + a_2 x_2 + ... + a_n x_n = S (S = half the sum)
x_1 + x_2 + ... + x_n = n / 2 (n = even)
Code in C++:
bool get_weighted_half(int* a, int* x, int pos, int sum_left, int choice_left)
{
// Picked too much
if (sum_left < 0)
return false;
// Picked enough!
if (choice_left == 0)
{
// Picked too little
if (sum_left > 0)
return false;
else
// Picked right size, right amount!
return true;
}
if (pos == -1)
// Nothing left!
return false;
// Not done yet...
x[pos] = 1;
if (get_weighted_half(a, x, pos - 1, sum_left - a[pos], choice_left - 1))
return true;
// x[pos] = 1 does not work
x[pos] = 0;
return (get_weighted_half(a, x, pos - 1, sum_left, choice_left));
}
For an input array
int a[8] = {1, 2, 3, 4, 5, 6, 7, 8};
int x[8] = {0};
int pos = 7, sum_left = 18, choice_left = 4;
get_weighted_half(a, x, pos, sum_left, choice_left);
the output will be
1, 2, 7, 8
Which is a solution, and not unique.
package main;
import java.util.ArrayList;
import java.util.List;
/*
Given a array of size n. Divide the array in to two arrays of size n/2,n/2. such that average of two arrays is equal.
*/
public class Main {
public static void main(String[] args) {
System.out.println("Begin ");
List<Integer> input = new ArrayList<Integer>();
List<Integer> output = new ArrayList<Integer>();
input.add(1);
input.add(2);
input.add(3);
input.add(4);
input.add(5);
/*input.add(10);
input.add(7);
input.add(8);
*/
try {
fill(input, output, 2, 5);
} catch (Exception e) {
System.out.println("Found");
}
System.out.println("End ");
}
private static void fill(List<Integer> left, List<Integer> solution, int depth, int target) throws Exception
{
if(depth == 0)
{
if(sum(solution) == target)
{
System.out.println(print(solution));
return;
//throw new Exception("found");
}
}
else
{
int i = 0;
while( i < left.size())
{
Integer current = left.get(i);
left.remove(current);
solution.add(current);
System.out.println("Left: " + print(left) + " - Solution: " + print(solution));
//System.out.println(current);
fill(left,solution,depth-1,target);
System.out.println("-----------------------------------------");
solution.remove(current);
left.add(current);
System.out.println("Left: " + print(left) + " - Solution: " + print(solution));
i++;
}
}
}
private static int sum(List<Integer> input)
{
int output = 0;
for (int i = 0; i < input.size(); i++) {
output += input.get(i);
}
return output;
}
private static String print(List<Integer> input)
{
String output = "";
for (int i = 0; i < input.size(); i++) {
output += input.get(i) + ",";
}
return output;
}
}
DP solution :
1. generate dp matrix upto K such that
a) k has 2 true (means there are two pairs of subset whose sum is K
b) check if two pairs are distinct and covering all elements of main set
c) if false then repeat above two steps till k reaches a optimal sum(like totalsum/tota no of elements)
import java.util.Arrays;
public class DevideEquel {
int[] array={4,4,6,7,7,6,3,3};
int n=array.length;
public static void main(String[] args) {
DevideEquel devideEquel=new DevideEquel();
Arrays.sort(devideEquel.array);
int mid=(devideEquel.n-1)/2;
for(int i=0;i<=mid;i++)
{
for(int j=devideEquel.n-1;j>mid;j--)
{
int temp=devideEquel.array[j];
devideEquel.array[j]=devideEquel.array[i];
devideEquel.array[i]=temp;
int left=0;
int right=0;
for(int f=0;f<=mid;f++)
{
left=left+devideEquel.array[f];
right=right+devideEquel.array[devideEquel.n-1-f];
}
if(left==right){
System.out.print("left="+left);
System.out.println(" right="+right);
for(int y=0;y<devideEquel.n;y++)
{
System.out.print(" "+devideEquel.array[y]);
}
return;
}
}
}
}
}
The inteviewers took a famous problem (partition into 2 arrays of equal sum) and they modified it to "average"
But average of 2 equal sized lists being equal is the same as the sum of 2 equal sized lists being equal.
So this is the PARTITION PROBLEM.
Please google it and study the wikipedia page.
This is one of those question where if you didn't know this problem before hand, you would either
1) Only do brute force bad solution
2) [Most keen people] Will get an incorrect greedy algorithm that seems to work
So those folks at Amazon were expecting you to know that average is same as sum and expected you to know the partition problem (not memorized, but know enough that greedy is wrong).
#include <stdio.h>
#include <stdbool.h>
#define end 4
bool done = false;
int total = 0;
int original[] = {1, 2, 3, 4};
void DivideArray(int * arr , int index , int start , int count , int sum);
int main()
{
int arr[end/2] , i;
for (i = 0 ; i < end ; i++) {
total = total + original[i];
}
DivideArray(arr , 0 , 0 , 1 ,0);
if (done) {
for(i = 0 ; i < (end/2) ; i++)
printf("%d ", arr[i]);
}
else
printf("elements not found to match the sum");
printf("\n\n");
}
void DivideArray(int * arr , int index , int start , int count , int sum)
{
int i;
sum = sum + original[start];
if (sum > (total/2))
return;
arr[index] = original[start];
if ((sum == (total/2)) && (count == (end/2))) {
done = true;
return;
}
if (count >= (end/2))
return;
for(i = start + 1 ; i < end ; i++) {
if(done)
return;
DivideArray(arr , index + 1 , i , count + 1 , sum);
}
}
Why can't we use following algorithm (haven't read comments intentionally)
1. Sort the array, complexity O(N*logN) in asc. order
2. Run through the array once (complexity is O(N)), ultimately it's gonna be O(N*logN)
void Split(int[] input, List<int> a1, List<a2>)
{
long sum1 = 0, sum2 = 0;
Sort(input);
for (int i = input.Length; i>=0; i--)
{
if (sum1 <= sum2)
{
sum1 += input[i];
a1.Add(input[i]);
}else
{
sum2 += input[i];
a2.Add(input[i]);
}
//If we're sure that sum/2 fits into long type - no problem, otherwise we need to manage it
//like if (sum1 >= Epsilon || sum2 >= Epsilon) {sum1-=Epsilon, sum2-=Epsilon}, where
//Epsilon is a bullet-proof limit that excepts overflows
}
if (sum1!= sum2)
Console.WriteLine("Average sums differ");
}
You can't use a greedy approach. See the example I gave earlier:
{1, 2, 30, 30, 30, 87}
array1 = {1, 30, 30} , array2 = {2, 30, 87}
However there is a solution {1,2,87} and {30,30,30}
Why? In my algorithm you get
A1 | A2
1. 87 |
2. 87 | 30
3.87 | 30 30
4. 87 | 303030
5. 87 2 | 30 30 30
6. 87 2 1 | 30 30 30
What's wrong, huh?
The only difference in your algorithm is that you take numbers in decreasing order. It's wrong by the same reason. It works for that example, but fails with examples like
{ 1, 20, 20, 20, 29, 30 } answer is {1, 29, 30} , {20,20,20} but your algorithm gives {30, 20, 1} and {29, 20, 20 }
and negative numbers { -87, -30, -30, -30, -2 , -1 } you get 6. -1 -2 -30 -30 -30 -87 | <empty array>
I think that the sum of all the elements of the input array should be even,
Steps:
1. Sort the array (number of elements in input array will always be even)
2. Will get 2 middle numbers. Put one in 1st output array and 2nd one in 2nd out put array.
3. Itrerate the input array from left side till the middle number alternatively put the elements in the out put arrays. like 0th position element in 1 st output array and 1st position element in 2nd out put array.
4. Irerate the right side of the input array reversly till mid of te inoput array and do the same.
Please let me know if this solution is feasible.
Thanks,
ankur
int[] val={1,3,8,4,5,6,7,8};
int lsum=val[0];
int rsum=val[val.length-1];
int i=0,j=0;
for(i=1,j=val.length-2;;){
if(i==j+1){
break;
}
if(lsum>rsum){
rsum+=val[j];
j--;
}else if(rsum>lsum){
lsum+=val[i];
i++;
}else{
rsum+=val[j];
j--;
lsum+=val[i];
i++;
}
}
if(lsum==rsum){
System.out.println("Found: [1,"+i+"]["+(i+1)+","+val.length+"]\tSum:"+lsum);
}else{
System.out.println("Not Found");
}
int[] val={1,3,8,4,5,6,7,8};
int lsum=val[0];
int rsum=val[val.length-1];
int i=0,j=0;
for(i=1,j=val.length-2;;){
if(i==j+1){
break;
}
if(lsum>rsum){
rsum+=val[j];
j--;
}else if(rsum>lsum){
lsum+=val[i];
i++;
}else{
rsum+=val[j];
j--;
lsum+=val[i];
i++;
}
}
if(lsum==rsum){
System.out.println("Found: [1,"+i+"]["+(i+1)+","+val.length+"]\tSum:"+lsum);
}else{
System.out.println("Not Found");
Assuming the number of elements in the array is even and the sum of elements is also even.
1) Sort the array.
2) Use two variables. One to store the sum of elements at indexes that leave a remainder of 0 or 4 when divided by 4. The other to store the sum of elements at indexes that leave a remainder of 1 or 2 when divided by 4.
3) If the two variables are equal then the array can be divided into two halfs with equal sum.
TC : O(n)
1. Sort the array
2. Start inserting elements into 2 arrays, while inserting the elements into the array, maintain its sum as well.
3. If the sum in array1 < array2, insert the element into array1 else into array2.
for step #1 - O(n log n)
for step #2 & 3 - O (n)
so totally its O (n log n) + O(n).
Let me know if somebody got a better approach.
You can't use a greedy approach. See the example I gave earlier:
{1, 2, 30, 30, 30, 87}
array1 = {1, 30, 30} , array2 = {2, 30, 87}
However there is a solution {1,2,87} and {30,30,30}
Just realised this approach may not work if there are duplicates.
Say Input = { 6, 6, 5, 4, 4, } which will split the numbers into
array1 = { 6, 5 } & array2 = {6, 4, 4 }
but the optimal result will be
array1 = { 6, 6 } & array2 = { 5, 4, 4 }
Other way to solve the problem is by using Partition Problem which is NP-Complete and got an exponential complexity ..
it may work but with small change. Sort in descending order
sort A in descending order.
TS = sum(A) // sum of all element in A
Create empty array B & C.
for i = 0 to size(A) -1
if ( TS/2 - sum(B) > TS/2-sum(C) ) {
if (A(i) + sum(B) < TS/2) {
add A(i) to B
} else {
add A(i) to C
}
} else {
if (A(i) + sum(C) < TS/2) {
add A(i) to C
} else {
add A(i) to B
}
}
1 sort the array.
2. Create two groups by picking elements in pairs but in alternate fashion.
Assuming after sorting array is a[1]....a[n]
gr1:(a[1],a[n]) (a[3], a[n-2]) so on
gr2: (a[2], a[n-1])(a[4], a[n-3]) so on
int[] val={1,3,8,4,5,6,7,8};
int lsum=val[0];
int rsum=val[val.length-1];
int i=0,j=0;
for(i=1,j=val.length-2;;){
if(i==j+1){
break;
}
if(lsum>rsum){
rsum+=val[j];
j--;
}else if(rsum>lsum){
lsum+=val[i];
i++;
}else{
rsum+=val[j];
j--;
lsum+=val[i];
i++;
}
}
if(lsum==rsum){
System.out.println("Found: [1,"+i+"]["+(i+1)+","+val.length+"]\tSum:"+lsum);
}else{
System.out.println("Not Found");
}
Let S = Sum(all numbers) / 2, the sum of the elements each array shall have. I suppose N is reasonably small, like N <= 40. One approach would be
- Miguel Oliveira August 29, 2013Work with 2 halves A and B of the array independently: A from indices [0, N/2-1] and B from [N/2, N-1].
Generate all possible sums of elements in array A. Use N/2 hash tables, one for each number of elements of the subsets, and put the sum of a subset in the corresponding hash table. There are 2^(N/2) subsets of A, this takes O(N/2 * 2^(N/2)) time.
Then generate all possible sums of B. For each subset of B, with X elements and sum Z, check if there is a subset of A in the hash table for sizes N/2-X with sum S-Z. There are also 2^(N/2) subsets and each lookup in a hash table takes O(1).
So this takes total time O(N/2 * 2^(N/2)) and O(2^(N/2)) space. For N=40, N/2 = 20 and 2^20 is ~1 million which is usually ok.