2
\$\begingroup\$

Given a positive integer, n, along with n non-negative integers, write a program or function that prints or returns the smallest non-negative integer that can be obtained by additions and subtractions between those numbers. You must use all of the input numbers.

The winner is the algorithm with the smallest big O time complexity. Ties will be broken by shortest code, in bytes. Please post your time complexity and your byte count along with your submission.

Examples

Input: 5 14 16 20 10 2
Output: 2

Two is the smallest number that can be obtained by adding or subtracting the given numbers, as shown by 16 + 14 - 20 - 10 + 2 = 2.

Input: 4 1 1 1 1
Output: 0

Input: 1 0
Output: 0

Input: 3 100 50 49
Output: 1

\$\endgroup\$
9
  • 1
    \$\begingroup\$ What is 'fastest'? \$\endgroup\$
    – user12166
    May 11 '15 at 0:50
  • \$\begingroup\$ It's the fastest algorithm \$\endgroup\$
    – Sherpinsky
    May 11 '15 at 0:52
  • 1
    \$\begingroup\$ Seems like grading by big O complexity will result in lots of many-way ties. How will these be resolved? Am I correct in assuming that every number in the input must be used exactly once? \$\endgroup\$
    – JohnE
    May 11 '15 at 1:28
  • 6
    \$\begingroup\$ This is the optimzation version of the partition problem, which is NP-hard, so you won't be getting any polynomial-time algorithms. \$\endgroup\$
    – xnor
    May 11 '15 at 8:31
  • 5
    \$\begingroup\$ There's two parameters at play here: the number of numbers, and their sizes. Different algorithms could make tradeoffs in the two. How will they be compared? (The complexity-theory default is to consider the bit-length of the input.) \$\endgroup\$
    – xnor
    May 11 '15 at 8:37

Browse other questions tagged or ask your own question.