CareerCup

An example would help in clarifying the question.

Is it sum of differences or difference of sums ?

Algo :

-> sort the numbers in increasing order
-> create two array(A1,A2), two variable sum1,sum2, both are zero initially.
-> start from i =  end(n-1) to j, where Array[j] >=0 and Array[j-1] < 0
    -> if(sum1 == sum2)
             add Array[i] to A1;sum1 += Array[i];
         else if(sum1 > sum2)
             add Array[i] to A2;sum2 += Array[i];
        else if(sum1 < sum2)
             add Array[i] to A1;sum1 += Array[i];
-> start from i =  start(0) to j-1, where Array[j] >=0 and Array[j-1] < 0
    -> if(sum1 == sum2)
             Sub Array[i] from A1;sum1 -= Array[i]
         else if(sum1 > sum2)
             Sub Array[i] from A1;sum1 -= Array[i];
        else if(sum1 < sum2)
             Sub Array[i] from A2;sum2 -= Array[i];

Add up all the Elements in the array which is say total. Construct an array , A[total] and find how many ways to sum up the value i ( i from 0 to total) and enter in A[total] array using DP(coin problem)

Now , start at A[total/2] and check if the value is 0 or not . If not zero , total/2 is the value and elements used to form total/2 is the solution. If it is zero, check A[total/2-1] and A[total/2+1] and check it is zero or not. Move in this fashion in both direction till you find an entry in Array
A which is not zero.

Here is the aproach,
1. know what should be the sum for arrays. ie S= nX(n+1)/2.
2. now divide S by 2 (two equal parts). ie D=S/2.
3. now iterate the elements of array collect them in separate array and sum. till arraySum >= D become true.
4. that part of collected array and remaining elements in the array is your answer.

What do you mean by "sum of difference"? And by 'equal' arrays, do you mean 'equal-sized' arrays? Thanks

An example would help in clarifying the question.

Is it sum of differences or difference of sums ?

I have got one solution, Its not O(n) Its just an idea, Please let me know how good is it :
Sort the array using stable sort which would take O(n) :
suppose we have array :
[6,7,15,17,12,18,20]
Sort it : [6,7,12,15,17,18,20]
Now, divide in two arrays taking alternate elements ;
a1 : [6,15,12,20]
a2 : [7,17,18]
check addition : a1 = 45 a2 = 39
Now The array which have small addition keep a pointer at its first [a2] and start comparing from last element of other array[a1]
Now compare :
step 1: 7 with 20 check difference and try to substract it from 45 and add in 39 if addition is not matching or greater move pointer in a1 to previous element :
Now 7 with 12...This goes up to comparing with 6. here try substract difference i.e. 1 from 45 and add in 39
Its 44 and 40 so addition of a1 > a2 swap 7 and 6 move pointer
from 7 to 17 start over again keeping pointer to last index of a2 continue the procedure...
step 2 : check if sum of a1 and a2 equal not : check if still addition a1 > a2
continue with step 1 by moving pointer of a2 to next element
keep on checking that addition of a1 should be greater than a2 and hould not drop below as we have to keep it minimum or equal

At one point u would get both additions 42
Stop.

This can go to O(n1*n2). This can`t be an answer for above question but just an idea.
n1 = elements in a1
n2 = elements in a2

It cann't be done in O(n) time.
In this link solution is explained. youtube.com/watch?v=GdnpQY2j064

Correct me if i'm wrong. but here is my approach.(which i think is right)
Given an array A[N], we want to find an index i such that
objective = Absolute value(Sum of elements(A[0] to A[i]) - Sum of Elements(A[i+1], A[i]) )
is minimized.

Now in a single pass, generate a cumulative array. C[N]

Now the objective = abs( sumof(A[1,i]) - sumof(A[i+1,N)) = abs(2*sum[A[1,i] - C[N])

Do a second pass over the array. and calculate objective for all i. keeping track of minimum and index.

This is a general purpose case to minimize the difference.

The only problem i see is with the phrasing of the question. which says. "into two equal arrays"
Any ways. feel free to comment. And btw the algo is O(N) time , and O(N) space

#include<iostream>
#include<limits>
#include<math.h>
using namespace std;
int main()                              
{
    int N=0;
    cout<<"input N"<<endl;
 cin>>N;
 int A[N];
 for(int i=0;i<N;++i)
 {
  cin>>A[i];
 }

 int cummulative[N];
 cummulative[0] = A[0];
 for(int i=1;i<N;++i)
 {
    cummulative[i] = cummulative[i-1]+A[i];
 }

 int min=std::numeric_limits<int>::max();
 int minI = -1;
 for(int i=0;i<N;++i)
 {
  int objective = abs(2*cummulative[i] - cummulative[N-1]);
  if(objective <min)
  {
    min=objective;
    minI = i;
  }
 }
 cout<<"Split"<<endl;
 cout<<"{";
 
 for(int i=0;i<N;i++)
 {
   cout<<A[i];
     if(i==minI) cout<<"},{";
 }
cout<<"}"<<endl<<"With Min = "<<min<<endl;
}

I think I managed to implement it in O(n). Can anybody check?

#include <stdio.h>
#include <stdlib.h>

void divide_array(int *arr, int len)
{
	int *s1;
	int *s2;
	int sums1 = 0;
	int s1i;
	int sums2 = 0;
	int s2i;
	int sum;
	int avg;
	int med = len / 2;
	int i;
	
	if (!arr || len == 0)
		return;
		
	if (len % 2 > 0) {
		printf("Array must have even number of elements.");
		return;
	}

	// Allocate both sets
	s1 = malloc(med * sizeof(int));
	s2 = malloc(med * sizeof(int));
	
	// Split in O(n)
	sum = 0;
	for (i = 0, s1i = 0, s2i = 0; i < len; i++) {
		// Sum and calculate average
		sum += arr[i];
		avg = sum / i;
		
		// No elements on s1 or s2 is already full. Add to s1.
		if (sums1 == 0 || s2i == med) {
			s1[s1i++] = arr[i];
			sums1 += arr[i];
		}
		// No elements on s2 or s1 is already full. Add to s2.
		else if (sums2 == 0 || s1i == med) {
			s2[s2i++] = arr[i];
			sums2 += arr[i];
		}
		else {
			// Sum of s1 is bigger than sum of s2
			// and the current element is smaller than average.
			// So, add to s1.
			if (sums1 >= sums2 && arr[i] <= avg) {
				s1[s1i++] = arr[i];
				sums1 += arr[i];
			// Sum of s2 is bigger than sum of s1
			// and the current element is smaller than average.
			// So, add to s2.
			} else if (sums2 >= sums1 && arr[i] <= avg) {
				s2[s2i++] = arr[i];
				sums2 += arr[i];
			} else {
				// If there are less elements on s1, add the current one.
				if (s1i <= s2i) {
					s1[s1i++] = arr[i];
					sums1 += arr[i];
				// Otherwise, add to s2
				} else {
					s2[s2i++] = arr[i];
					sums2 += arr[i];
				}
			}
		}
	}

	// Print sets
	printf("S1 ");
	for (i = 0; i < med; i++) {
		printf("%d ", s1[i]);
	}
	printf(" sum=%d\n", sums1);

	printf("S2 ");
	for (i = 0; i < med; i++) {
		printf("%d ", s2[i]);
	}
	printf(" sum=%d\n", sums2);

	// Free memory
	free(s1);
	free(s2);
}

int main(void)
{
	int arr[] = {3, 1, 1, 2, 2, 1, 4, 9, 3, 2, 9, 1};
	int len = sizeof(arr) / sizeof(arr[0]);
	divide_array(arr, len);
	return 0;
}

Here is a DP approach in python. I did not make it efficient but it is working fine I suppose.
DP works as long as the total sum of elements in the array is not too large.
I am also assuming all elements are positive.

idea: Assume you pick elements 1, 2, ..., k and would like to find a subset summing to "exactly" C. We have
SUM[k][C] = either SUM[k - 1][C] && (not picking ak) OR SUM[k - 1][C - ak] && (picking ak)
Eventually you have SUM[N - 1][x] for 0 <= x <= Cmax (sum of all elements) to be either true or false. If it is true, a subset summing to that value exists.

The rest is easy. You just need to break it into some c and Cmax - c and make c and Cmax - c as close as possible. Assuming c < Cmax - c, you just need to check Cmax / 2 and decrease "c" until for some value, SUM[N - 1][c] = TRUE

main_set = {1, 2, 4, 11, 44, 20}
main_set = list(main_set)

Cmax = sum(main_set)
N = len(main_set)

# init a list
dp_table = []
decision = []
for n in range(0, N):
    x = []
    y = []

for k in range(0, Cmax + 1):
        x.append(k == 0)
        y.append([])
    dp_table.append(x)
    decision.append(y)

for i in range(0, N):
    for c in range(0, Cmax + 1):
        ai = main_set[i]      
        if c > 0:  
            dp_table[i][c] = False
        if i > 0:
            if dp_table[i - 1][c]:
                dp_table[i][c] = True
                decision[i][c].append(-ai)                    
        if c - ai > -1:
            if dp_table[i - 1][c - ai]:
                dp_table[i][c] = True
                decision[i][c].append(ai)
     

c = Cmax / 2
while not dp_table[N - 1][c]:
    c = c - 1
    if c < 0:
        print "WHAT?!"
        exit(-1)        

    

print "The smaller or equal subset will sum up to ", c
print "And the larger or equal subset will sum up to ", Cmax - c
d = []
nc = c
for k in range(N - 1, -1, -1):
    if len(decision[k][nc]) > 0:
        dec = decision[k][nc][0]
        if dec > 0:
            nc = nc - dec
            d.append(dec)
print "One of the sets is : ", d , " summing up to ", sum(d)

1. Sort array (nlogn)
2. Proceed with pairs of extreme left and right, put them in two arrays alternatively.
3. Take care of odd and even number of such pairs.

# first sort the array in descending order then apply the function

void devide(int a[20])
{
int i=0,sumb=0,sumc=0,j=0,k=0,b[10],c[10];
sumb=b[j++]=a[0];
sumc=c[k++]=a[1];
for(i=2;i<limit;i++)
{
if(sumb>sumc)
{
sumc+=(c[k++]=a[i]);
}
else
{
sumb+=(b[j++]=a[i]);
}
}
// for(i=0;i<limit;i++)
// printf("\n%d\n",a[i]);
printf("sum b=%d nd sum of c %d",sumb,sumc);

}
void main()
{ int i=0,a[20];

for(i=0;i<limit;i++)
scanf("%d",&a[i]);
sortDesc(a);
devide(a);

}

1) Initialize lists L and R.
2) Sort the array: O(nlogn)
3) Start from the end of the array - add the element (current largest) to the array that would minimize the difference between the two lists.

def badsolution(arrayinput):
	arrayinput.sort()
	L=[]
	R=[]

	for i in xrange(1,len(arrayinput)+1):
		if abs(sum(L+[arrayinput[-i]])-sum(R)) < abs(sum(R+[arrayinput[-i]])-sum(L)):
			L.append(arrayinput[-i])
		else:
			R.append(arrayinput[-i])

	return L,R

The logic is simple, no sorting nothing required.
1) First element from the array goes in array 1, second element goes to array 2, a variable will save the difference between the 2 arrays (lets say A1[1]-A2[1]).
2) if the variable is positive, start adding next element to A2 and subtract the value from variable till the variable has negative value.
3) if the variable is negative, start adding next element to A1 and add the value to variable till the variable has positive value.
4) repeat step 4.

It is a case of Subset Sum problem. As someone already mentioned, it can be solved in pseudo polynomial time using DP where the space complexity is O(sum of all elements * # elements)

public class DivideArray {

public DivideArray(int[] array){

int sum = 0;
int[] setA,setB;
for(int i=0;i<array.length;i++){
sum +=array[i];
}
sum=sum/2;
int arraysum=0 ;
setA = new int[array.length];
setB = new int[array.length];
int a=0;
int b=0;
for(int i=0;i<array.length;i++){

if(array[i]+arraysum<=sum){
setA[a++]=array[i];
arraysum+=array[i];
}
else
setB[b++]=array[i];
}

System.out.println(arraysum);
}
}

1) Try to use subset sum way of doing the recursive
2) Make two list, one the element selected like we add element in the subset list and the other list with remaining elements.
3) Instead of if (sum < number) we can actually have something like, we are not done with processing of all the elements and add the entry into hashMap
4) In hashMap at ever-recursive call store absolute of sum(selectList) - (remainingList) as a key and value as selectList,remainingList
5) Once the complete recursive finishes
6) we can find the min key and theri corresponding pairs.

Simple it is just implement following algo.
1)Divide sumation of array by 2.Store result in limit.
2)sort the array.
3)Go on adding array element one by one until sum>limit.
4)Add rest of the array to form second set.

Obviously this problem can best solved by Dynamic Programming.
This problem is reducible to 0-1 knapsack problem. Where S/2 is the size of bag. ( Considering S to be sum of entire Array )

package algo.interview;

public class DivideSubarray {

	private static void dividesubarray(int a[])
	{
		int totalSum = 0 ;
		for(int i = 0; i < a.length; ++i)
			totalSum += a[i] ;
	
		int halfSum = totalSum / 2 ;
		
		int leftSum = 0 ;
		int i = 0;
		for(; i < a.length && leftSum + a[i] <= halfSum; ++i)
		{
			leftSum += a[i];
		}
	
		if(leftSum != halfSum)
		{
			int nextElementDiff = Math.abs(totalSum - (leftSum + a[i]));
			if(nextElementDiff < (totalSum - leftSum))
			{
				leftSum += a[i];
				i++;
			}
		}
		
		System.out.println("Total:" +  totalSum + " LeftSum:" + leftSum + " Start:0" + " End" + (i-1));
	}
	
	public static void main(String[] args) {
		
		dividesubarray(new int[]{1,2,3,4,5,6,7,8});
		dividesubarray(new int[]{9,2,10,11,1,3,4});
	}
}

package com.javafries.knapsack;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 
 * @author vishal.naik
 *
 */
public class ArrayDivider {

	public static void main(String[] args) {
		
		// Array to be divided
		int [] array = {9,2,10,11,1,3,4};
		
		System.out.println("Original array.");
		printArray(array);
		
		divideArrayBasedOnMinimumDifference(array);
	}


	/**
	 * This method divides array in two sublists such that
	 * difference between sum of the elements of individual
	 * sublist is minimum.
	 * </br>
	 * If you divide given array in 'l1' and 'l2' then
	 * (sum of elements of 'l1') - (sum of elements of 'l2') 
	 * should be minimum
	 * 
	 * @param array , not null
	 */
	private static void divideArrayBasedOnMinimumDifference(int[] array) {

		// Sort array.
		Arrays.sort(array);
		
		// Array after sorting
		System.out.println("Sorted array:");
		printArray(array);

		int totalSum = sumOfArrayElements(array);
		int halfSum = totalSum /2;
		int len = array.length;
		
		// Lists to hold sub-lists
		List<Integer> subList1 = new ArrayList<>();
		List<Integer> subList2 = new ArrayList<>();
		
		
		// Iterate array in reverse order 
		for(int i = len - 1,sum=0; i >= 0; i--) {
			
			// Add element to list 1 if 
			// (sum of elements of list 1) + (current element of array)
			// is less than or equal to half sum
			if (sum + array[i] <= halfSum) {
				subList1.add(array[i]);
				sum += array[i];
			} else {			// else add element to list 2
				subList2.add(array[i]);
			}
		}
		
		System.out.println("Sub list 1:");
		printList(subList1);
		
		System.out.println("Sub list 2:");
		printList(subList2);
	}
	
	/***
	 * Returns sum of array elements.
	 * @param array , not null
	 * @return sum of array elements
	 */
	private static int sumOfArrayElements(final int[] array) {
		int sum = 0;
		for (int i : array) {
			sum += i;
		}
		return sum;
	}
	
	/**
	 * Prints array.
	 * @param array , not null
	 */
	private static void printArray(final int[] array) {
		for (int i : array) {
			System.out.print(i + " ");
		}
		System.out.println();
	}
	
	/**
	 * Prints array.
	 * @param array , not null
	 */
	private static void printList(final List<Integer> list) {
		for (Integer i : list) {
			System.out.print(i + " ");
		}
		System.out.println();
	}
}

Please visit java-fries site. Copy following search string and search in google to find the link

Divide an array in two sub-arrays such that the difference between sum of the elements of individual sub-array is minimum

public class inAnotinB {

	public static void main(String[] args) {
		
		int[] A = {1, 3, 4, 6,8,10, 17, 34} ;
		int[] B = {2, 8, 17, 33, 44, 66, 89, 100, 123}; 

		int largest = A[A.length-1] > B[B.length-1]?  A[A.length-1] : B[B.length-1];
		int smallest = A[A.length-1] < B[B.length-1]?  A[A.length-1] : B[B.length-1];
		
		int i=0,j=0;
		
		while(smallest != largest) {
			if(A[i] == B[j]) {
				smallest = A[i];
				i++;
				j++;
			} else if(A[i] < B[j]) {
				System.out.print(A[i]+" ");
				smallest = A[i];
				i++;
			} else {
				smallest = B[j];
				System.out.print(B[j]+" ");
				j++;
			}
			
			if(i>=A.length) {
				for (; j < B.length; j++) {
					System.out.print(B[j] + " ");
					smallest = B[j];
				}
			}
			
			if(j>=B.length) {
				for (; i < A.length; i++) {
					System.out.print(A[i] + " ");
					smallest = A[i];
				}
			}
			
		}
	}

}

/* I did not sort the array . Sort the array in descending order and then iterate through array
it will work for all the above case which got failed . */

import java.util.ArrayList;
import java.util.Scanner;

public class FIndOptimalArray {
int [] arr;
ArrayList<Integer> a1 = new ArrayList<>();
ArrayList<Integer> a2 = new ArrayList<>();
int sum1,sum2;
int diff;
int size;
public void getSizeOfArray(){
Scanner sc = new Scanner(System.in);
System.out.println("Enter the number of integer");
size = sc.nextInt();
arr = new int[size];

System.out.println("Enter the numbers one by one");
for (int i=0; i<size; i++) {
arr[i] = sc.nextInt();
}
}

public int findDifference() {
for (int i=0; i<size; i++) {
if (diff == 0) {
a1.add(arr[i]);
sum1 += arr[i];
}
else if (diff < 0) {
a1.add(arr[i]);
sum1 += arr[i];
}
else {
a2.add(arr[i]);
sum2 += arr[i];
}
diff = sum1 - sum2;
}

return Math.abs(diff);

}

}

This is an NP-Complete problem in itself, and it can not be solved in O(n) for un-sorted array
if array is sorted then it can be done in O(n)

If array is sorted it costs very less to partition(take one element from lowest/smallest end and add to the max element till the sets are of equal size)

Hence cost of partition should be of order O(n.logn)

If you mean to minimize {Sum(elements of array1) - Sum(elements of array2)}, then follow:
1. Sort the original array.
2. Alternatively place the pairs {ith element, (length-i)th element} to each of the two resulting arrays.

This is a simple DP problem, you just need to get familiar with 1-0 backpack Template.