Minimum sum of numbers in an array

Source: Asked to me on quora ( cseblog.quora.com )

Problem:

 Given an array of n positive numbers (n ~ 100000), what is the algorithmic approach to find the minimum possible sum (>=0) by using all the numbers in an array?

Example 1:
1 2 2 3 4
Answer : 0 (-1+2-2-3+4)

Example 2:
2 3 4 7 13
Answer: 1 (+2-3-4-7+13)




Solution:

Highlight the part between the * symbols for the answer.
* This is the partition problem: assigning +/- signs to use all numbers means splitting them into two groups; the minimum |sum| = S - 2T where S is the total and T is the largest subset sum not exceeding S/2.

Algorithm: subset-sum DP. Compute reachable sums up to floor(S/2) with a bitset: start with bit 0 set, and for each number x shift the bitset left by x and OR it in. The highest set bit T <= S/2 gives the answer S - 2T. Time O(n * S / 64) with bitset words, O(S) memory - fine when the values are bounded (the problem is NP-hard in general, so no algorithm polynomial in n alone exists unless P = NP; for huge values use the FPTAS or greedy heuristics).

Sanity checks: {1,2,2,3,4}: S = 12, best T <= 6 is 6 (2+4 or 1+2+3) -> 0. {2,3,4,7,13}: S = 29, best T <= 14 is 14 (7+4+3) -> 29 - 28 = 1. Matches the examples.

Note the tempting greedy "repeatedly subtract the two largest" (or heap balanced-assignment) is NOT always optimal - e.g. {8,7,6,5,4}: greedy gives 2, optimal is 0 (8+4 = 7+... 8+7 = 15, 6+5+4 = 15).

Solution by an Anonymous commenter (subset-sum/knapsack DP) from the comments; greedy counterexample and AI verification. *

Comments

  1. Unknown1:15 PM, August 14, 2014

    Since the array is large and unsorted (assumption), I think a greedy approach with backtracking is advisable.

    Mohan S N

    ReplyDelete
  2. Unknown4:49 PM, August 14, 2014

    Assuming that the numbers are integers, this problem can be solved using integer knapsack problem. Let the sum of all the numbers in the array be S. Think of a bag of size S/2. The problem now becomes making a subset from the array having sum less than or equal to S/2. Just be careful while obtaining S, as it might be larger than maximum allowed value for a positive integer. Use a proper database to hold that.

    ReplyDelete
  3. Sambhav Gupta2:18 AM, August 16, 2014

    At every iteration, find the largest 2 integers in the array ('n' steps), remove and subtract them, and insert the difference back to the array. Do this 'n' times. We have the result in O(n^2) time.

    ReplyDelete
    Replies
    1. Sachin Dayanand Aglave11:32 AM, August 23, 2014

      nice one :)

      Delete
    2. Unknown7:50 PM, November 24, 2014

      Consider the following example 3,3,3,7,8, 8
      optimal is 3+3+3+7-8-8 =0
      But your method finds the optimal in the set 3,3,3,7,0 which is not 0 clearly.

      So the method don't work if the largest 2 integers belong to same category

      Delete
  4. Khalil Sawant6:42 PM, August 16, 2014

    Are we over estimating this problem ?

    http://www.quora.com/Given-an-array-of-n-positive-numbers-n-100000-what-is-the-algorithmic-approach-to-find-the-minimum-possible-sum-0-by-using-all-the-numbers-in-an-array/answer/Khalil-Sawant

    ReplyDelete
  5. ADITYA P.5:26 PM, August 29, 2014

    i dont get the problem ... in example 1 where is -2 ?? all are positive numberz??

    ReplyDelete
  6. Manoj Agarwal8:13 PM, September 29, 2014

    Create the max heap (O(n)). Maintain two running counters. Take the first number from heap and add it to counter1, take the 2nd number form the heap and add it to counter2. After that, take the next number from the heap and add it to the counter that minimizes |counter1 - counter2|, i.e., always add that number to the counter that is currently smaller of the two. Keep doing this and you will get the answer in O(n log n). Proof: Is by induction...

    ReplyDelete
  7. timequalsmoney4:57 AM, September 13, 2016

    Recursive Approach (inefficient though(2^n complexity) but I Like Recursion!):
    int minsum(int* arr,int n, int m)//n is number of elements left to consider, m is the min sum
    {
    if(n==1)
    {
    if *arr>=m return *arr;
    else return infinity;
    int a=minsum(arr+1,n-1,m-*arr);
    int b=minsum(arr+1,n-1,m+*arr);
    return(a+*arr<b-*arr?a+*arr:b-*arr);
    }
    in main call minsum(arr,n,0)

    ReplyDelete

Post a Comment

Popular posts from this blog

Polya's Urn Problem: Expected Balls in the Smaller Urn

Puzzle: There are two urns with one ball each. Each of subsequent n-2 balls is placed into one of these urns, with probability proportional to the number of balls already in that urn. What is the expected number of balls in the smaller sized urn? Source: P. Winkler's Puzzles book. (Chapter: Probability). Solution: Highlight the part between the * symbols for the answer. * This problem can be reformulated as the following problem. Suppose I have a stack of black cards and one red card. Initially I take red card in my hand. Now I add black cards randomly between any two cards (so, initially its either above or below red). Note that the probability that I add the card above the red card, when x-1 is the number of cards above red and y-1 is the number of cards below red is x/(x+y). Let the problem be if red card is dividing the black cards into two sets, what is the expected number of black cards in the smaller section. So, we see that the two problems are equivalent. No...
Read more

Lion and Man in a Circular Cage: Can the Lion Catch the Tamer?

Source: Asked to me by Pramod Ganapathi (PhD Student at Stony Brook University) Problem: A lion and a lion tamer are enclosed within a circular cage. If they move at the same speed but are both restricted by the cage, can the lion catch the lion tamer? (Represent the cage by a circle, and the lion and lion tamer as two point masses within it.) Solution: Highlight the part between the * symbols for the answer. * Answer: surprisingly, no - the tamer can avoid being caught forever. This is the famous Lion and Man problem, posed in the 1930s and settled by Besicovitch; the proof appears in Littlewood's "A Mathematician's Miscellany" (and opens Bollobas's "The Art of Mathematics"). What the lion CAN do (Rado's strategy): move to the center, then always stay on the radius through the tamer, using any spare speed to move outward. Since the lion runs on a smaller circle, it can match the tamer's angular position while steadily increasing its radiu...
Read more

Expected Tosses for Consecutive Heads: 2 Heads vs 3 Heads Puzzle

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process. 1) Calculate P{X>Y} 2) What's the expected value of X 3) What's the expected value of Y This is probably the hardest puzzle I have ever put on my blog. Hence, I will post its solution in the post directly rather than on comment. Solution: 1) (Solved by me finally after 13 months :)) Make a state diagram. Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently. So, (0,3) (1,3) are final accepted states and (2,0) (2,1) (2,2) (2,3) are failure states. If you get tails, your contribution to the state reaches to "0" f(State) = P(X>Y | "State" configuration initially) ...
Read more