## Minimum Impossible Sum

### April 24, 2015

There is a simple solution that just scans through the sorted list:

`(define (min-impossible-sum xs)`

(let loop ((xs (sort < xs)) (x 1))

(if (or (null? xs) (< x (car xs))) x

(loop (cdr xs) (+ x (car xs))))))

At each step the minimum impossible sum of the numbers seen so far is calculated, starting from 1, which is the minimum impossible sum of no numbers. As soon as the next input number is greater than the running total, the function stops and returns the current minimum impossible sum; otherwise, the current input number is added to the running total and the next input number is considered. Here’s an example:

`> (min-impossible-sum '(4 13 2 3 1))`

11

Time complexity is O(*n*) plus the cost of the sort; with comparison-based sorts, that’s O(*n* log *n*), but if you use some kind of counting sort or radix sort you can reduce the total cost to O(*n*). You can run the program at http://ideone.com/manfov.

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

In Python.

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)

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

@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.

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

;-)

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

A sample run, printing the output of both functions.