# 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)$$

```python
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
```