CareerCup

there is a good DP solution provided here
://people.csail.mit.edu/bdean/6.046/dp/

Classic DP, balanced partition.

NPC
You can easily reduce Set Partition to this one.

With or without re-arrangement? If without re-arrangment, then it is pretty easy (even bruce force method only has a O(n^2) time complexity.)

geniusxsy is right. Although it can be solved by DP, it is still in NPC. Not all problems solvable by DP is O(N^2).

This problem is pseudo-polynomial, which means it's polynomial to the NUMERIC VALUE of N, but not the input size (unless numbers are encoded in unary.)

guys what is DP...i hv no idea...plz pas on links regarding DP

Hey Anonymous, DP = dynamic programming

en.wikipedia.org/wiki/Dynamic_programming

Generate all combinations.
Find the sum of the halves.
keep track of the one that has the least difference in sums.

geniusxsy is right.Its a DP problem but it is NP-complete actually if we look at the sample input

[1,2,3,4]

worst case we need to calculate all possible partitions (sub partitions ) .
That way its same as generating subsets so would be of the order 2^ n-1 .Or there is no polynomial solution available hence it is NPC.

1.Construct a BST using the array
2. Select the max value for array1
3. Select the second max value for array2.
4. Now it is array1's turn to select a number
5. compare the difference btw sum of array1 and sum of array2
6. if ( array1 > array2)
then select the closest value which would bridge the difference
else if ( array2 > array1)
then select the closest value which would bridge the difference
else (array2 == array1)
then select the next max value;

Repeat step 6 till every number from input array is selected

not sure about this... plz evaluate

you should sort it and then go over it from largest to smallest
if a[i] increase the gap then throw to 2nd array
else throw to first array.
O(nlogn+n)=O(nlogn)

What about this? This method will find and save the pivotal element of the original array.
This pivotal element is the last element of the lhs partition. Complexity O(2n)?

int main(int argc, char* argv[])
{
    int array[] = {1,2,3,4,5,6,7,8,9};
    int size = sizeof(array)/sizeof(int);

    int total = 0;
    int imbalance = -1;
    int pivotal_elem = -1;

    split_array(array, size, size, &total, &imbalance, &pivotal_elem);
  
    return 0;
}

int split_array(int* curr_elem,
                int  curr_size,
                int  orig_size,
                int* total,
                int* imbalance,
                int* pivotal_elem)
{
    int prev_rhs_elems = 0;

    *total += *curr_elem;

    if (curr_size > 1)
    {
        prev_rhs_elems = split_array(curr_elem+1, curr_size-1, orig_size, total, imbalance, pivotal_elem);
    }
    
    int rhs = *curr_elem + prev_rhs_elems;
    int lhs = *total - rhs;

    int temp = (rhs > lhs) ? (rhs-lhs) : (lhs-rhs);

    if (*imbalance < 0 || *imbalance > temp)
    {
        *imbalance = temp;
        *pivotal_elem = orig_size - curr_size - 1;
    }

    return *curr_elem;
}

As said earlier, this is NP complete.

Why waste time? Sorting might be fast, but still it is a waste of time.

int ar[] = ...
ar = sort(ar);

if(ar.length < 3) return ar;

for(i=0, j=n; i<j; i+=2; j-=2)
{

 int temp = ar[i+1]; ar[i+1] = ar[n-1]; ar[n-1] = t;

}

first sort the array..take two arrays arr1 and arr2.....now scan the main array from the end and place last element in aar1 and second last element in arr2...then place third last also in arr2 and fourth last in arr1...proceed this way until we reach the the first element of main array...thats it now the arr1 and arr2 will have minimum difference between them

step 1. find the sum of elements in the array.--O(n)
step 2. find the val = sum/2 -- o(1)
step 3. sort the array.--O(n log n)
step 4. find the set of elements whose sum is equals to val. ---O(n)

overall TC is O(n log n)

please correct me if some thing is wrong.

btw DP is O(n^3)

@Bala is there a mathematical proof for your algorithm?

A better algorithm by greedy approach.
1. Sort array
2. for each element: if sum(array1)<sum(array2) then put it in first array else into second.
3. Once all elements are split. iteratively minimize difference value by moving elements from one to other
while(true)
diffValue = sum(array1)-sum(array2)
by binary search find closer value to difValue/2 in array2 and move it to the other or vice versa
compute difference again if no change then break.

vector<int> array1,array2;
vector<int> elements; //contains the array to be split
long sumOfArray1=0,sumOfArray2=0;

sort(elements.begin(),elements.end()); //its better to sort

//For each element
for(int i=0;i<elements.size();i++){
//if first array has lesser sum then push 'i'the element it in the firstarray
(sumOfArray1<=sumOfArray2) ?array1.push_back(elements[i]):array2.push_back(elements[i]);
}
//once the values are split into two arrays
//do as in step 3 //hint:: use lower_bound from STL and find closer value to difference/2 and move it to the other set.

A better algorithm by greedy approach.
1. Sort array
2. for each element: if sum(array1)<sum(array2) then put it in first array else into second.
3. Once all elements are split. iteratively minimize difference value by moving elements from one to other
while(true)
diffValue = sum(array1)-sum(array2)
by binary search find closer value to difValue/2 in array2 and move it to the other or vice versa
compute difference again if no change then break.

vector<int> array1,array2;
vector<int> elements; //contains the array to be split
long sumOfArray1=0,sumOfArray2=0;

sort(elements.begin(),elements.end()); //its better to sort

//For each element
for(int i=0;i<elements.size();i++){
//if first array has lesser sum then push 'i'the element it in the firstarray
(sumOfArray1<=sumOfArray2) ?array1.push_back(elements[i]):array2.push_back(elements[i]);
}
//once the values are split into two arrays
//do as in step 3 //hint:: use lower_bound from STL and find closer value to difference/2 and move it to the other set.

Simple problem...
Just have an array c[] for cumulative sum.
and the answer just follows.

Eg.

1,2,3,-4,5

cumulative arrray: 1,3,6,2,7

now just see all the partitions: diff= a[n]-2*c[i], if i is the place of partition.
Take the maximum.
Algorithm is clearly O(n)

If all numbers are positive
1) sort in decreasing order
2) for each element, if sum(array1) < sum(array2) then add to array1 else add to array2.
Done. This is the optimal solution, no need to "iteratively minimize" (as chenna suggested).

If numbers are both positive and negative
1) order in decreasing order of their absolute values. O(n log n)
2) if a_i >= 0, do the same as above. If a_i < 0, do the opposite. O(n)
Done.

No DP needed. BTW, I'd like to see somebody actually solving this using DP, I personally don't see how.

I have been trying to figure out how to prove that the algorithm above indeed produces the optimal solution, so far I am not exactly sure. Induction seems like the best choice but I got stuck halfway through.

O(n) in space and time.

1. take 2 arrays, T and S.
2. traverse the main array and keep adding elements on the following condition..
(Let the next number be x, let the current sum of the two arrays be S and T respectively)
if (x>0) add x to the array with lesser sum. (ie, if S<T, add x to S)
if (x<0) add x to the array with greater sum. (ie, if S>T, add x to S)

This algo "seems" to be correct. I cant prove it correctness, but havent been able to find a case of failure.
Please point out my mistake if I gt wrong somewhere.

O(n) in space and time.

1. take 2 arrays, T and S.
2. traverse the main array and keep adding elements on the following condition..
(Let the next number be x, let the current sum of the two arrays be S and T respectively)
if (x>0) add x to the array with lesser sum. (ie, if S<T, add x to S)
if (x<0) add x to the array with greater sum. (ie, if S>T, add x to S)

This algo "seems" to be correct. I cant prove it correctness, but havent been able to find a case of failure.
Please point out my mistake if I gt wrong somewhere.

I think, we can this problem by using MAX HEAP.

1. array A[n] is given two you. We know size of array i.e n
2. Two Split arrays S1[n1] S2[n2] . here n1, n2 are sizes of split arrays.
3. Construct MAX HEAP by using A[n] elements.
4. for each i =MaxHeapElement() // for all n elements
if ( SUM(S1) > SUM(s2) )
{
add i to S2[]
n2++;
}
else
{
add i to S1[] ;
n1++;
}
5. n1 + n2 == n .

6. SUM(S1) ~= SUM(S2) ;

7. Time complexity O(nlogn)

Problem for O(nlogn) algorithms: {5,4,3,3,3}. Algorithms suggest {5,3} and {4,3,3} but {4,5} and {3,3,3} better. Correcting could end without finding optimal, since maybe we should be at a bigger difference before finding optimal.
Consider correcting {50,30,22} and {50,30,18} we would never find {50,50} and {30,30,22,18} - NP hard problem. It takes O(2^n) to solve.

convert the array into a BST.

Now do an inorder traversal. While doing the traversal, put the min value into arr1 and the next min value to arr2. In the next step, put max value to arr2 and the next value to arr1.

For ex: inorder 1 2 3 4 12 13 15 17

arr1 1 4 12 17
arr2 3 13 15

Please help me to code this statement.

"Java codes that will accept 20 different numbers both negative and positive and their sum"

Please send code to email; daddokor77@gmail.com

First of all, since the problem mentions sub-arrays, I think this isn't the same Balanced Partition problem that many have assumed it is. So it's actually much simpler and can be solved in O(n).

First, we iterate once to find the total. Then we iterate again, this time comparing the difference between the left and the right sub-arrays, and see if this difference is the smallest we have seen so far. At the end, we return the index associated with the minimum difference. The index is the index of the last element that we should include in the left sub-array.

int findEquilibrium(int[] arr) {
	int total = 0;
	for(int n : arr) {
		total += n;
	}
	int min = Integer.MAX_VALUE;
	int equilibrium = 0;
	int left = 0;
	int right = total;
	for(int i=0; i<arr.length; i++) {
		left += arr[i];
		right -= arr[i];
		int diff = Math.abs(left-right);
		if(diff < min) {
			equilibrium = i;
			min = diff;
		}
	}
	return equilibrium;
}

1. Sort the array (increasing order)
2. Make two variables that tracks current sum of each array, sum1, sum2
2. Loop from end and put two elements in two arrays, and add those values to sum1 and sum2.
3. For the next two elements, put the bigger one to the side that has lower sum, and smaller one to the other. Add respective elements to sum.

Hey guys,

If I am not wrong, we can add all the negative numbers in one array and all the positive numbers in another array and then (negative array) - (positive array)

sort the array using quicksort.........now store the 1st half of array into array1 and second half into array 2

sort the array in ascending order. Put all elements at odd indexes into array1 and all elements at even indexes into array2. Then, sum(array1) - sum(array2) will be minimum

1. Find average: Add all the elements in the array and divide it by 2.
2. Now get the ceiling and floor of the average. So if the avg is 6.5, one answer is 7.0 and another is 6.0
3. Make one sub-array whose summation of elements is 7.0 and another one whose is 6.0. And that's the answer.
The difference would be always 1(if the sum%2 !=0) or 0(otherwise). I did it myself with O(n^2).

Solution is O(nlgn)
Sort
take largest number ; put into one sequence
for any other number (+ve) add it to lesser sum sequence
for any other number (-ve) add it to greater sum sequence