DEV Community 👩‍💻👨‍💻

DEV Community 👩‍💻👨‍💻 is a community of 963,274 amazing developers

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

Create account Log in staff staff

Posted on

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.


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.



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 with your suggestions!

Top comments (4)

bubbler4 profile image

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


{...}     ⍝ 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
soorajsnblaze333 profile image
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;
n8chz profile image
Lorraine Lee • Edited on


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])

def solve(numbers)
  (1..).each do |n|
    smalls ={|i| i <= n}
    next if smalls.include? n
    return n if smalls.sum < n
    return n unless contains?(smalls, n)
masterroshan profile image
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

Take a look at this:


Go to your customization settings to nudge your home feed to show content more relevant to your developer experience level. 🛠