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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://lei-d.gitbook.io/leetcode/math/smallest-non-constructible-value.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.