Smallest Non-constructible Value
Given an array of positive integers (representing coins), find the smallest value that cannot be constructed from those integers.
Reference: Elements of Programming Interviews in python, page 189
Example 1:
Example 2:
Solution:
Idea:
Key observation here is, when the integers are sorted, we can always track the highest constructible value by doing a cumulative sum of the sorted integers.
At any point if the next integer is larger than
max_constructible + 1
, then there is no way to constructmax_constructible + 1
. Example 1 and example 2 illustrates this fact.
Time Complexity: for sorting, for searching.
Space Complexity:
Last updated