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

Question

I came across this question in a coding competition-

You're given an array of positive integers and 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. This sum should be >= 0. For example : Array = {1,2,4,5} then sum = 0 as we change sign of 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. I would then iteratively decrease 2*(sorted array value) from the sum-starting from the largest number - till sum becomes 0 or till it becomes negative.

But my solution is wrong. Take 12,13,14,15,16,50. My code would 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 knap-sack problem

consider this problem:

you are given n integers, and obviously, you can calculate the sum of these number, suppose it is S

you are now required to choose a set of numbers from them, and aims to sum these chosen numbers to be as close to S/2 as possible

this can be done using a DP algorithm which is very similar to knap-sack 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 was irritated by the other answers, saying something about knap-sack.

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

To me it looks more like makespan scheduling where you have two machines and have to assign all the jobs to them such that the makespan is minimal.

So you can think about it as two stacks and you try to minimize the difference of their height.

An 3/2-approximation algorithm is this:

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

You get your approximation by turning the sign of all objects on the smaller stack negative summing the numbers up. (i.e. computing the absolute difference of the both stacks)

If you search for minimal makespan scheduling, you can find a PTAS and an exact algorithm that needs exponential time in the length of the list.

Answer 3

Sorting won't work here because this cannot be solved by Greedy approach just like in 0-1 Knapsack. You can think this way, every element in the array has 2 choices either be negative or positive. You can develop a recursive solution by either selecting a number (one branch) or not selecting it (the other branch)

Here's an implementation of what I was saying. The code can be improved in several ways. Sorry if it has very less comments. I am running short of 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;
}

Answer 4

I wrote the above code and it seems to be working.

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