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!
Top comments (4)
APL (using Dyalog APL):
(Use the bookmarklet on this post to see the code with APL font and syntax highlighting.)
Not very fast (
O(2^n)
wheren
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:
Ruby:
Not sure if this is efficient