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

Overview

How can we solve this?

Trying to solve this with bruteforce will be complicated, there has got to be a better way. A note to remember is that when you are given an input array we can always sort it. Often, sorting the array leads to a solution.

Sorting the array, is giving a small hint we may use to our advantage. We are looking for the minimum amount of change and we have an ascending order array.

After some analysis and proof by contradiction, it is revealed that, if we sum the coins at each iteration and if the next number is greater than current sum plus one, then current sum plus one is the solution.

Flow Diagram

Sorting is key to the solution. Then just checking if the iterated number is greater than current sum plus one would lead to the solution.

Time Complexity

The solution starts off by sorting the array once and then going through the array once, that will give us O(nlogn) time complexity, because of the initial sort. A good sorting algorithm will be O(nlog).

Space Complexity

The space is constant. No extra space is needed to solve this algorithm. The space complexity is O(1). Nice.

Java Source Code

public int find(int[] coins) {
        Arrays.sort(coins);

        var currentChangeCreated = 0;
        for(var coin : coins) {
            final var maxChangeCanBeCreated = currentChangeCreated + 1;
            if(coin > maxChangeCanBeCreated) {
                return maxChangeCanBeCreated;
            }

            currentChangeCreated = currentChangeCreated + coin;
        }
        return currentChangeCreated + 1;
    }

Conclusion

In the business world, everyone is paid in two coins: cash and experience. Take the experience first; the cash will come later.

Harold S. Green