CareerCup

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

Work 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.

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

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]

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?

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

Asked here before: change the question id in the above url to: 2622

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

First of all this is not possible for each and every data.

say, array has only 2 elements : 1,1000000

Whatever we do, we'll end up with 2 arrays with average 1 and 1000000 respectively.

If possible for a particular array, I think DP would be best approach

Can you give me solution to thiis array a[] = { 2,3,5,6,8}
sum = 24 avg = 12 but no combination will give sum of 12

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 ?

But to divide an array in n/2,n/2 ,we have to have even size array?How about if array is of size 5 which is odd then 5/2,5/2 what ?

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

}

Check out my solution :

"github.com/amitgoswami/ALGO_TRIALS/blob/dev/CommonAlgoQuestions/SubsetSumEqualNos/src/SubsetSumEqual.java"

it is a link add https as prefix

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)

the above logic picking the elements in alternate fashion works

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

this can be integer knapsack with size of sum/2 and weight of each item equals one

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

Suppose a array has element(n*n) according to its index number and divide this array into n parts that each parts have equal sum??,Please Help me to slove this

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

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.

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