## DEV Community is a community of 662,780 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Daily Challenge #283 - Simple Missing Sum dev.to staff
The hardworking team behind dev.to ❤️

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 yo+challenge@dev.to with your suggestions!

## Discussion (4) 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
``````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 • Edited

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
`````` 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
``````