Smallest non-constructable value

Given an array of integers (representing coins), find the smallest value that cannot be constructed from those integers.

Solution

• Key observation here is, when the integers are sorted, we can always track the highest constructable value by doing a cumulative sum of the sorted integers
• At any point if the next integer is larger than max_constructable_so_far + 1, then we have found our smallest non-constructable value

Code

def smallest_non_constractible_value(arr)
    return nil if arr.nil?

    arr.sort

    max_constructable = 0
    arr.each do |e|
        if e > max_constructable + 1
            break
        end

        max_constructable += e
    end

    return max_constructable + 1
end

Time complexity

O(n log n) to sort, and O(n) to find the result, overall O(n log n)