Daily Challenge #283 - Simple Missing Sum

In this challenge, we will calculate the minimum number that is not a possible sum from a list of positive integers.

Examples

solve([1,2,8,7]) = 4
we can get 1, 2, 3 (from 1+2), but we cannot get 4. 4 is the smallest number not retrievable from the list.

solve([4,1,2,3,12]) = 11
We can get 1, 2, 3, 4, 4+1=5, 4+2=6, 4+3=7, 4+3+1=8, 4+3+2=9, 4+3+2+1=10. But we can't get to 11.

solve([2,3,2,3,4,2,12,3]) = 1. We cannot get 1.

Tests

solve([4,2,8,3,1])
solve([4,2,7,3,1])
solve([1,2,8,7])
solve([4,2,12,3])

Good luck!

---

This challenge comes from KenKamau on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email [e-mail] with your suggestions!

Comments

[Bubbler]

APL (using Dyalog APL):

solve←{⊃(⍳1++/⍵)~⊃(+,,)/⍵}

(Use the bookmarklet on this post to see the code with APL font and syntax highlighting.)

Not very fast (O(2^n) where n is the length of the input array), but definitely gets the job done, concisely. Demo is here. Note that an array of ones (e.g. [1, 1, 1, 1]) is a corner case, because the answer is one higher than the sum of the input numbers.

Explanation:

solve←{⊃(⍳1++/⍵)~⊃(+,,)/⍵}
{...}     ⍝ Define a function
⊃(...)/⍵  ⍝ Reduce the input by...
+,,       ⍝  concatenation of both sides and
          ⍝  pairwise sum
~         ⍝ Remove the numbers in the above from
(⍳1++/⍵)  ⍝ Generate 1..(sum of ⍵ + 1)
⊃         ⍝ Take the first (smallest) number

[Sooraj (PS)]

const getCombinations = (arr) => {
  let combinations = [];
  for (let i = 1; i < (Math.pow(2, arr.length)); i++) {
    let subsetArray = [];
    for (let j = 0; j < arr.length; j++)
      if (i & Math.pow(2, j)) subsetArray.push(arr[j]);
    let sum = subsetArray.reduce((a, b) => a + b);
    if (!combinations.includes(sum)) combinations.push(sum);
  }
  return combinations;
}

const solve = (arr) => {
  let max = arr.reduce((a, b) => a + b);
  let combinations = getCombinations(arr);
  for (let index = 1; index < max; index++)
    if (!combinations.includes(index)) return index;
}

[Lorraine Lee]

Ruby:

def contains?(numbers, n)
  return true if n == 0
  (0...numbers.count).each do |i|
    right = numbers.drop(i+1)
    next if right.include? n
    return true if contains?(numbers.take(i)+right, n-numbers[i])
  end
  false
end

def solve(numbers)
  (1..).each do |n|
    smalls = numbers.select{|i| i <= n}
    next if smalls.include? n
    return n if smalls.sum < n
    return n unless contains?(smalls, n)
  end
end

[TJ Johnson]

Not sure if this is efficient

from itertools import combinations, chain
def solve(numbers):
    combs = [list(combinations(numbers, x)) for x in range(1,len(numbers) + 1)]
    flattened_combs = list(chain.from_iterable(combs))
    sums = [sum(x) for x in flattened_combs]
    x = 1
    while(x in sums):
        x = x + 1
    return x