CareerCup

import java.util.Arrays;
import java.util.Collections;

public class MinSum {

public static void main(String[] args) {
Integer obj[] ={1,3,4,5};
int sum = 0;
Arrays.sort(obj,Collections.reverseOrder());
for(int i=0;i<obj.length;i++)
System.out.println(obj[i]);

for(int j=0;j<obj.length;j++)
{int elem = obj[j];
if(j ==0)
{
sum = obj[j];
continue;
}

if(sum > elem)
{
elem = -elem;
sum = sum + elem;
}
else
{if(sum <elem && sum > 0)
{
elem = -elem;
sum=sum+elem;
}else
{
sum = sum + elem;
}
}
}
System.out.println(Math.abs(sum));
}}

private int getSum(int[]arr){
		int sum=0;
		for (int i = 0; i < arr.length; i++) {
			sum=sum+arr[i];
		}
		return sum;
	}
	
	private void knapsack() {
		// given an array of positive integers and that you are allowed to 
		//change the sign of any of the integers whenever you require.
		//write a program to calculate the minimum sum of this array.
		
		
		int [] arr = new int[]{0,9,8,7,6,5,4,3};
		
		//sort the array
		for (int i = 0; i < arr.length; i++) {
			
			
			for (int j = 0; j < arr.length; j++) {
				
				
				if(i!=j){
					
					if(arr[i]<arr[j]){
						int temp=arr[i];
						arr[i]=arr[j];
						arr[j]=temp;
					}
				}
			}
		}
		
			
			for (int j = 1; j < arr.length; j++) {
				//check total sum considering number as +ve and then -ve
				//depending on the min sum consider the sign of the number
				int temp = arr[j];
				arr[j]=-arr[j]; //negative
				int k = getSum(arr);
				arr[j]=-arr[j];//positive
				int l=getSum(arr);
				//compare min sum
					if(k<l){
						if(k>0)
						arr[j]=-temp;
					}
						
					else
						if(l>0)
						arr[j]=temp;
					
			}
			
			//print array
			for (int j = 0; j < arr.length; j++) {
				System.out.println("="+arr[j]);
			}
	}

Here is my solution: Run time Complexity is 0(n^2)

public class PartitionSum {
public static int minimum =0;
public static void main(String[] args){

//int[] arr = new int[]{1,5,9,10,3,6,4,2,8,7}; // input array
//int[] arr = new int[]{1,2,3,4,5,6,7,8,9,10}; // input array
int[] arr = new int[]{4,12,22,32,42,52,62,72,82,92};
// 4,12,22,32,42,52,62,72,82,92
int n = arr.length ;
boolean[] flag = new boolean[n];
int[] par = new int[n]; // to store data after partiton

minimum = maximum(arr)- minimum(arr);

findPartition(arr, flag, n, par);
for(int i =0 ; i<n ;i++){
System.out.println(par[i]);
}
}

public static void findPartition(int[] arr, boolean[] flag,int n,int[] par){
int leftSum = 0;
int rightSum = 0;
int left =0;
int right = n-1;
for(int i=0; i<n; i++){
if(flag[i] == true) continue;
int j = findNearest(arr,flag,n,i);
System.out.println("i "+i +" j : "+j);
flag[i] = true;
flag[j] = true;
if(leftSum <= rightSum){
par[left++] = Math.max(arr[i], arr[j]);
leftSum += Math.max(arr[i], arr[j]);
par[right--] = Math.min(arr[i], arr[j]);
rightSum += Math.min(arr[i], arr[j]);
}else{
par[left++] = Math.min(arr[i], arr[j]);
leftSum += Math.min(arr[i], arr[j]);
par[right--] = Math.max(arr[i], arr[j]);
rightSum += Math.max(arr[i], arr[j]);
}
}

if(leftSum > rightSum){
for(int i = right+1; i<n;i++)
par[i] = -par[i];
}else{
for(int i = 0; i<left;i++)
par[i] = -par[i];
}
System.out.println("-------------------------------");
for(int i =0 ;i < n ; i++){
System.out.print(par[i]+",");
}
}

public static int findNearest(int[] arr, boolean[] flag, int n, int index){
int minIndex = 0;
int min = minimum;
for(int i = 0 ; i< arr.length;i++){
if(i == index)
continue;
if(flag[i] == true)
continue;

if(arr[index]-arr[i] > 0)
{ if((arr[index] - arr[i]) < min)
{
min = arr[index]-arr[i];
minIndex = i;
}
}
else
{ if(arr[i] - arr[index] < min)
{
min = arr[i] - arr[index];
minIndex = i;
}
}
}

return minIndex;
}

public static int maximum(int[] arr){
int max = 0;
for(int i=0;i<arr.length;i++){
if(max < arr[i])
max = arr[i];
}
return max;
}

public static int minimum(int[] arr){
int min = 0;
for(int i=0;i<arr.length;i++){
if(min > arr[i])
min = arr[i];
}
return min;
}


}

I think its like to find the two sets of integers where sum difference between two set is min.
Then return the min difference.

with Dynamic programming I have implemented it in O(n^3) + O(n^2) solution,
the solution is similar to matrix chain multiplication solution, where we calculate M(i,j){minimum possible sum when we consider the sub-array starting from "i" and ends with "j"}, But the minimum value computation will be different.

Algorithm:
1. Sort given array (say, in ascending order) ( Time: nlogn )
2. Loop once through array and find total sum - ( Time: n )
3. Start from right most element - ( Time: n )
4. See if current element can be made negative (for i = n - 1 to 0, both inclusive )

curr = a[i];
min_sum = total_sum - 2 * curr;
if ( min_sum >= 0 )
{
    a[i] = curr * -1;
    total_sum = min_sum; // update sum
}
if ( min_sum == 0 ) break; // because you can't minimize than that

5. When you reach first element, you would have made sufficient elements negative or you would have broke out from the loop.
TC: O(n log n)
SC: O(1)

Advantages:
1. Time complexity is nlogn
Disadvantages:
1. Modifies the input array

Here is the working C function (tested for all inputs in other answers):

int ModifyArray( int * a, int n )
{
	int i, sum = 0;
	if (!a) return -1;
	if ( n <= 0 ) return -1;
	// sort the input array in increasing order
	qsort( &a[0], n, sizeof(int), compare );
	// find total sum in one loop
	for ( i = 0; i < n; ++i )
		sum += a[i];
	// actual algorithm
	// scan from right to left
	// see if each element's twice can be subtracted from total sum
	for ( i = n - 1; i >= 0; --i ) {
		int element = a[i];
		int min_sum = sum - 2 * element;
		if ( min_sum >= 0 ) {
			a[i] = element * -1;
			sum = min_sum;
		}
		if ( min_sum == 0 ) break; // early termination
	}
	return sum;
}

e.g,
4,5,10,19=sum should be zero
Greedy algo
sort the given numbers.
try to mimize the sum of the last two digits
19-10=9
new series is
4,5,9
again try to minimize the sum of last two digits
9-5=4;
new series is
4,4
again try to minimize the sum of last two digits
4-4=0
ans is 0
Check it for other cases and tell me if its write
the series now

It is basically subset problem i.e can u find a subset which sums upto half of the total... have to solve using knapsack problem

Problem is solved using dynamic programming. We need to do a bit of pre-processing before invoking dynamic programming.

1. Sum up all the elements and let the sum be S
2. If S is odd, then the numbers can be partitioned into two sets, such that the difference of the sum of their elements is at least 1. If S is even their difference could be at least 0.
3. In either case, we need to figure out if there exists a subset of the elements in original array whose sum equals to S/2. If such a set exists, the other elements can put into another set which partitions the array into two sets and their sums would be equal.(sums would be roughly equal if S is odd an also depends on the distribution of numbers)
4.Once the set is identified, mark the elements with a -ve sign.
5. The summation of these numbers would yield a minimum number >=0.

Follows is a full implementation in java. Inputs are given using space as delimiter.
Eg: 5 3 7 2 4 6 1

import java.util.ArrayList;
import java.util.Scanner;
import java.util.regex.Pattern;

public class PartitionProblem {
	static ArrayList<Integer> input = new ArrayList<Integer>();

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		Pattern pattern = Pattern.compile(System.getProperty("line.separator")
				+ "|\\s");
		scanner.useDelimiter(pattern);

		int intval, sum = 0;

		while (scanner.hasNextInt()) {
			intval = scanner.nextInt();
			input.add(intval);
			sum += intval;
		}

		boolean[][] vals = new boolean[sum / 2 + 1][input.size() + 1];

		for (int j = 0; j <= input.size(); j++) {
			vals[0][j] = true;
		}

		for (int j = 1; j <= sum / 2; j++) {
			vals[j][0] = false;
		}

		for (int i = 1; i <= sum / 2; i++) {
			for (int j = 1; j <= input.size(); j++) {
				vals[i][j] = vals[i][j - 1];

				if (!vals[i][j]) {
					if ((i - input.get(j - 1)) >= 0) {
						vals[i][j] = vals[i - input.get(j - 1)][j - 1];
					} else {
						vals[i][j] = false;
					}
				}

			}
		}

		if (vals[sum / 2][input.size()]) {
			int i = sum / 2, j = input.size();

			while (i >= 0 && j > 0) {

				if (!vals[i][j - 1]) {
					i -= input.get(j - 1);
					input.set(j-1, -input.get(j - 1));
				}
				j--;
			}
		}		
		System.out.println(input);		
	}
}

I am assuming the code to be bug-free. Feel free to fix any issues.

in python:

def minsum(arr):
arr2 = arr[0:]
temp = max(arr2)

for i in range(len(arr2)):
if temp >0:
if len(arr2)>1:
arr2.remove(max(arr2))
temp = temp-max(arr2)
else:
return temp
else:
if len(arr2)>1:
arr2.remove(max(arr2))
temp = temp+max(arr2)
else:
return temp
return temp

This is the famous Partition Set problem, where the total set is divided into two subsets such that the difference between the sum of elements is minimum. It can be easily solved in O(sum/2)(n) time using back-pointers to find out the elements in the sets.

This comment has been deleted.

1.- Sort the array from high to low
2.- Initialize two accumulator with the first two numbers of the array
3.- Create two arrays
4.- If (sum1 - sum2 >= 0) {sum2 += next element of array; array2.add(index of the element); }
else { sum1 += next element of array; array1.add(index of the element); }
5.- Repeat step 4 until the end of array
6.- If (sum1 >= sum2) convert to negative elements of array2
else convert to negative elements of array1

import java.io.*;
import java.util.*;
 
public class Balpart
{
    public static void main (String [] args) throws IOException
     {
        int sum = 0;
        
        System.out.println("Enter the number of array elements");
        Scanner input = new Scanner(System.in);
        int N = input.nextInt();
        
        int[] array = new int[N];
        System.out.println("Enter the Positive elements of the array");
        
        for(int member = 0; member < N ; member++)
        {
            array[member] = input.nextInt();
            sum += array[member];      
        }
        
        boolean [] sol = new boolean [sum / 2 + 1];
        
        sol [0] = true;//empty array

        for (int i : array)
        {
        	for (int j = sum / 2; j >= i; j--)
            {
        		if (sol [j - i])
                sol [j] = true;
        	}
        }

                      

            int halfsumcloser = sum / 2;

            for (; !sol [halfsumcloser]; halfsumcloser--);

        System.out.println ("The Minimum sum After partioning the array is :" +((sum - halfsumcloser) - halfsumcloser));

          

        }

}

import java.util.HashSet;


public class MinSumFromArrayChangingSigns {


	public static void main(String[] args) {
		int[] array = new int[] {1,98,99,100};
		System.out.println(getMinSum(array));
	}

	public static int getMinSum(int[] array) {
		sortInDescendingOrder(array);
		HashSet<Integer> plusSet = new HashSet<Integer>();
		HashSet<Integer> minusSet = new HashSet<Integer>();
		int plusSetSum=0, minusSetSum=0;
		for (int i : array) {
			if (plusSetSum <= minusSetSum) {
				plusSet.add(i);
				plusSetSum += i;
			} else {
				minusSet.add(i);
				minusSetSum += i;
			}
		}
		return Math.abs(plusSetSum - minusSetSum);
	}

	public static void sortInDescendingOrder(int[] array) {
		int i=0,j=0,temp=0;
		for (i = 0; i<array.length; i++) {
			for (j=i+1; j<array.length; j++) {
				if (array[j] > array[i]) {
					temp = array[i];
					array[i] = array[j];
					array[j]=temp;
				}
			}
		}
	}

}

I think the problem is about finding the minimum positive sum. The solution is trivial otherwise.

Sum all abs. Take sum/2 . And standard subset problem with sum closes to sum/2 O(logn)

This is an NP-complete problem. If one can find the solution to the problem of "finding k numbers in an array that add upto a given sum" , this problem can be solved.

Wikipedia -> Knapsack Problem