2
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
Sherpinsky
Posted 2015-05-11T00:48:33.317
Reputation: 21
1What is 'fastest'? – None – 2015-05-11T00:50:56.697
It's the fastest algorithm – Sherpinsky – 2015-05-11T00:52:27.690
The tag suggests that it's the smallest big O time complexity. Is that what you are intending?
– None – 2015-05-11T00:53:28.947Yes, the challenge is to find the smallest big O complexity algorithm – Sherpinsky – 2015-05-11T00:54:42.253
1Seems 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? – JohnE – 2015-05-11T01:28:07.397
I was thinking about that. It can't be execution time, so it should be the length of the code – Sherpinsky – 2015-05-11T01:30:09.783
Can you add a couple more examples? – Def – 2015-05-11T05:59:23.397
6
This is the optimzation version of the partition problem, which is NP-hard, so you won't be getting any polynomial-time algorithms.
– xnor – 2015-05-11T08:31:02.3135There'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 – 2015-05-11T08:37:14.743