How to Solve the Non-Constructible Change problem

One of the more common coin and change problem is getting the exact change with the least amount of coins. However with the problem we are going to solve, there is a bit of variation. In this problem we are given an array of coins and we are looking to find the lowest amount we cannot make with the coins we have. The coins in the array are not necessarily unique, so we could possibly have multiples of each coin. We also can only use each number or coin in the array once.

The brute force method would be to loop through the array and find the every single combination or sum of coins available. Then we check to see if there is a number in between that we cannot be made with the coins. This method would be really inefficient and would most likely be too slow to be accepted as an answer.

Although it would be ideal to have O(n) time complexity, it is not always possible to solve in a timely matter. Other times, a problem such as binary search starts off already at O(n log(n) time due to the nature of its array being in a sorted state.

Like a binary search, we can start off the problem by sorting the given array. This way we can traverse the problem from the left. By sorting the array, it allows us to work on this problem in another perspective. Just by looking at it, we know we can make change of twelve seeing that we can add five and seven. But what about the numbers after? If we add up all the numbers prior to twenty-two, we get nineteen. What if we add another one to it? We can’t because we don’t have another one in the array to add. We’ve found our answer, but the keep take away is the plus one value.

With that being said, we can iterate through and stop at every index to see if its current value is greater than all the previous coins plus one. If the current value is greater, then we can return that previous coin plus one since it the lowest value we cannot make. If we iterate through the whole array and not get the value, then the answer would but the total value of all our coins plus one. Below is how we would write out the solution in Javascript.

With that we can wrap it up and say the time complexity is O(n log(n)) time due to the sort function on the array and O(1) space because we only have one output.