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:

Input: A = [1, 2, 4]
Output: 8
Explanation: With subsets of A, we can construct values 1, 2, 3, 4, 5, 6, 7.

Example 2:

Input: A = [1, 2, 5]
Output: 4
Explanation: With subsets of A, we can construct values 1, 2, 3, 5, 6, 7, 8.

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 construct max_constructible + 1. Example 1 and example 2 illustrates this fact.

Time Complexity: $O(\log{n})$ for sorting, $O(n)$ for searching.

Space Complexity: $O(1)$

def smallest_non_constructible_value(A):
    # linear search
    max_constructible = 0
    for a in sorted(A):
        if a > max_constructible + 1
            break
        max_constructible += e
    return max_constructible + 1

PreviousMultiply Two Integers NextSORT5

Last updated 4 years ago

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 construct max_constructible + 1. Example 1 and example 2 illustrates this fact.

Time Complexity:

O(\log{n})

for sorting,

O(n)

for searching.

Space Complexity:

O(1)

def smallest_non_constructible_value(A):
    # linear search
    max_constructible = 0
    for a in sorted(A):
        if a > max_constructible + 1
            break
        max_constructible += e
    return max_constructible + 1