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.

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
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: