Given that you can change the sign of numbers, find the Minimum Sum of array

Question

I came across this question in a coding contest -

You are given an array of positive integers and are allowed to change the sign of any of the integers whenever you need. Write a program to calculate the minimum amount of this array. This sum should be> = 0. For example: Array = {1,2,4,5}, then sum = 0 when changing the signs 1 and 5 {-1,2,4, -5}

My solution to the problem was to sort the array and find the sum of all the members. Then I would iteratively decrease the 2 * value (sorted array value) from the sum, starting with the largest number - until the sum becomes 0 or until it becomes negative.

But my decision is wrong. Take 12,13,14,15,16,50. My code will change 50 to -50 and stop (i.e. Min sum = 20). But the answer should be 12, -13, -14, -15, -16,50 (min sum = 4)

Answer 1

this problem can be changed to a problem with a knap bag

consider this problem:

you are given n integers, and obviously you can calculate the sum of these numbers, suppose that S

Now you need to select a set of numbers from them and the aim is to summarize these selected numbers as close as possible to S / 2

this can be done using the DP algorithm, which is very similar to a knap bag problem

can you do it now? :)

this post is just a hint, if you need more help, I can give more details

Answer 2

I wrote the code above and it seems to work.

Correct me if I am wrong!

public int minimumSum(int[] array) { int counter1, counter2, minimumSum; int n = array.length; counter1 = array[n-1]; counter2 = array[n-2]; // It is assumed that the array is sorted. int i = n-3; while(i>=0) { if(counter1 > counter2) { counter2 = counter2 + array[i]; } else { counter1 = counter1 + array[i]; } i--; } if(counter1 > counter2) { minimumSum = counter1 - counter2; } else minimumSum = counter2 - counter1; return minimumSum ; } 

Answer 3

Other answers annoyed me, saying something about a knap bag.

This is not something like Knap-Sack.

Knap-Sack means you have goal S and a list of weights A , and you are looking for a subset A that sums up to S

Your problem is much simpler because you know that you need to accept all numbers and just change the sign of some.

So you can think of it as two stacks, and you are trying to minimize the difference in height. This is an autonomous planning task, and it can be solved using the greedyal algorithm. For a code example, see Augustus answer .

• Sort list (max to min)
• for each object, put it on the stack with the smallest height

You get your decision by turning the sign of all objects onto a smaller stack, negating the total number of numbers. (i.e. calculating the absolute difference of both stacks)

Answer 4

Sorting will not work here because it is not possible to solve using Greedy, as in 0-1 Knapsack. You may think so, each element of the array has two options: negative or positive. You can develop a recursive solution by either selecting a number (one branch) or not selecting it (another branch)

Here is an implementation of what I said. The code can be improved in several ways. Sorry if he has very few comments. I do not have much time.

 #include "iostream" #include <algorithm> using namespace std; int *arr,*flag,mini=1000; int* sol; //Flag array is used to see which all elements are selected in that call of the function void find_difference(int* arr,int* flag,int n,int current,int *sol) { if(current==n)return; int sum0=0, sum1=0,entered=0; flag[current]=1; //Selecting the current indexed number for (int i = 0; i < n; ++i) { if(flag[i]==0) { sum0=sum0+arr[i]; } else { sum1=sum1+arr[i]; } } if(abs(sum0-sum1)<mini) { mini=abs(sum0-sum1); for (int j = 0; j < n; ++j) { sol[j]=flag[j]; //Remebering the optimal solution } } find_difference(arr,flag,n,current+1,sol); //Moving to the next index to perform the same operation (selecting or not selecting it) flag[current]=0; // Not selecting it for (int i = 0; i < n; ++i) { if(flag[i]==0) { sum0=sum0+arr[i]; } else { sum1=sum1+arr[i]; } } if(abs(sum0-sum1) < mini) { mini=abs(sum0-sum1); for (int j = 0; j < n; ++j) { sol[j]=flag[j]; } } find_difference(arr,flag,n,current+1,sol); } int main(int argc, char const *argv[]) { int n; cout<<"Enter size: "; cin>>n; cout<<"Enter the numbers: " arr= new int[n]; flag= new int[n]; sol= new int[n]; for (int i = 0; i < n; ++i) { cin>>arr[i]; flag[i]=0; sol[i]=0; } find_difference(arr,flag,n,0,sol); cout<<"Min = "<<mini<<endl; cout<<"One set is: "; for (int i = 0; i < n; ++i) { if (sol[i]==1) { cout<<arr[i]<<" "; } } cout<<"\nOther set is: "; for (int i = 0; i < n; ++i) { if (sol[i]==0) { cout<<arr[i]<<" "; } } cout<<"\n"; return 0; }