# Add or subtract numbers to find the smallest non-negative integer [closed]

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

• What is 'fastest'?
– user12166
May 11 '15 at 0:50
• It's the fastest algorithm May 11 '15 at 0:52
• 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? May 11 '15 at 1:28
• This is the optimzation version of the partition problem, which is NP-hard, so you won't be getting any polynomial-time algorithms.
– xnor
May 11 '15 at 8:31
• 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.)
– xnor
May 11 '15 at 8:37