## Minimum Impossible Sum

### April 24, 2015

We have today another from our inexhaustible list of interview questions:

Given a list of positive integers, find the smallest number that cannot be calculated as the sum of the integers in the list. For instance, given the integers 4, 13, 2, 3 and 1, the smallest number that cannot be calculated as the sum of the integers in the list is 11.

Your task is to write a program that solves the interview question. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 6 Responses to “Minimum Impossible Sum”

1. mvaneerde said

Wow, I was *sure* this would require an O(2^n) solution, but the O(n) solution (assuming sorted input) is so elegant.

2. Paul said

In Python.

```def impsum(seq):
runsum = 0
for e in sorted(seq):
if e > runsum + 1:
break
runsum += e
return runsum + 1
```
3. Rutger said

Finding minimum is easy with sort and a loop of max n iterations.
Added couple of methods to find them all (within a given range)

```#mis.py
import random
import itertools

# The #combinations of a list is 2**(len(list))
# set param iterations lower than this number and try to be lucky
# set param iterations higher to increase confidence (but also running time)
def has_sum_random(n, list_of_positive_integers, iterations):
i = 0
while i < iterations:
i += 1
l = list_of_positive_integers[:]
total = 0
while total < n and l:
total += l.pop(random.randrange(len(l)))
if total == n:
return True
return False

# tries all combinations of the list to match the sum to n
def has_sum_deterministic(n, list_of_positive_integers):
for i in range(len(list_of_positive_integers)+1):
combinations = itertools.combinations(list_of_positive_integers, i)
for c in combinations:
if sum(c) == n:
return True
return False

def minimum_impossible_sum(list_of_positive_integers):
s = 1
for e in sorted(list_of_positive_integers):
if e > s:
return s
s += e
return s

list_of_positive_integers = [4, 13, 2, 3, 1]
print minimum_impossible_sum(list_of_positive_integers)
for n in range(min(list_of_positive_integers), sum(list_of_positive_integers)+1):
print n,
print has_sum_random(n, list_of_positive_integers, 2**(len(list_of_positive_integers)+2)),
print has_sum_deterministic(n, list_of_positive_integers)

list_of_positive_integers = range(1, 30)
print minimum_impossible_sum(list_of_positive_integers)
for n in range(min(list_of_positive_integers), sum(list_of_positive_integers)+1):
print n,
print has_sum_random(n, list_of_positive_integers, 1000),
print has_sum_deterministic(n, list_of_positive_integers)
```

For [4, 13, 2, 3, 1] it finds
1 True True
2 True True
3 True True
4 True True
5 True True
6 True True
7 True True
8 True True
9 True True
10 True True
11 False False
12 False False
13 True True
14 True True
15 True True
16 True True
17 True True
18 True True
19 True True
20 True True
21 True True
22 True True
23 True True

4. programmingpraxis said

@mvaneerde: As an exercise, why don’t you write the O(2**n) solution and show it to us. Or if not that, an O(n**2) solution. Or some other time complexity. It is often instructive to be able to compare such solutions.

5. Jussi Piitulainen said

I’m not sure if this is O(2^n) or if it’s worse than that. Very roughly, it computes the powerbag of 2^n elements up to 2^n times; the append and map in P may or may not affect the complexity class. What next? Ordering the powerbag by the sum in order to walk it only once?
``` (define (conser a) (lambda (d) (cons a d)))```

``` (define (P B)   (if (null? B) '(())       (let ((S (P (cdr B))))         (append S (map (conser (car B)) S))))) (define (min-non-sum B)   (let s ((PB (P B)) (m 0))     (if (null? PB) m         (if (= (apply + (car PB)) m)             (s (P B) (+ m 1))             (s (cdr PB) m))))) ```

```; (length (P '(3 1 4 1))) => 16 ; (min-non-sum '(3 1 4 1)) => 10 ; (min-non-sum '(4 13 2 3 1)) => 11 ; (min-non-sum '()) => 1 ; (min-non-sum '(1)) => 2 ;-) ```

6. Globules said

A Haskell solution. The more efficient version is basically the same as Paul’s Python function.

```import Control.Monad (filterM, liftM)
import Data.List ((\\), sort)
import System.Environment (getArgs)

-- Minimum impossible sum.  Brute force version.
mis' :: [Integer] -> Integer
mis' =  head . ([1..] \\) . map sum . powerSet
where powerSet = filterM (const [True, False])

-- Minimum impossible sum.  More efficient version.
mis :: [Integer] -> Integer
mis xs = let ys = sort xs
in head . dropLE ys \$ scanl (+) 1 ys
where dropLE (a:as) (b:bs) | a <= b    = dropLE as bs
| otherwise = b:bs
dropLE _ bs = bs

main :: IO ()
main = do
xs <- liftM (map read) getArgs
mapM_ (print . mis ) xs
mapM_ (print . mis') xs
```

A sample run, printing the output of both functions.

```./minimpsum "[4, 13, 2, 3, 1]"
11
11
```