Non-Constructible Change

Tags

Non-Constructible Change

Category

Arrays

Difficulty

Easy

Problem Statement

Given an array of positive integers representing coin denominations, find the minimum amount of change that you cannot create using any combination of the coins. If the array is empty, the answer is 1.

Intuition

If we sort the coins and process them in ascending order, we can maintain a running sum representing the maximum contiguous change we can produce (from 1 to that sum). When we encounter a coin whose value exceeds currentChange + 1, there is a gap — we cannot make currentChange + 1. This greedy insight works because all coins up to the current one can combine to cover every value from 1 to currentChange.

Approach

  1. Sort the coins in ascending order.
  2. Initialize currentChangeCreated = 0.
  3. Iterate through each coin:
    • If the coin value is greater than currentChangeCreated + 1, then currentChangeCreated + 1 is the answer.
    • Otherwise, add the coin value to currentChangeCreated.
  4. If all coins are processed without finding a gap, return currentChangeCreated + 1.

Pseudocode

function nonConstructibleChange(coins):
    sort(coins)
    currentChangeCreated = 0
    for coin in coins:
        if coin > currentChangeCreated + 1:
            return currentChangeCreated + 1
        currentChangeCreated += coin
    return currentChangeCreated + 1

Time & Space Complexity

  • Time: O(n log n) — dominated by the sort step. The subsequent loop is O(n).
  • Space: O(1) — if sorting is done in-place; O(n) otherwise depending on the sort implementation.

Key Insights

  • The invariant is: after processing coins so far, we can make every value from 1 to currentChangeCreated.
  • When a new coin c satisfies c <= currentChangeCreated + 1, the range extends to currentChangeCreated + c.
  • When c > currentChangeCreated + 1, there is a gap at currentChangeCreated + 1 that no combination of remaining (larger) coins can fill.
  • Sorting is essential — processing coins out of order breaks the invariant.

Edge Cases

  • Empty array — return 1 (cannot make any change).
  • All coins are 1 — can make change from 1 to n, answer is n + 1.
  • First coin is greater than 1 — answer is 1 immediately.
  • Single coin of value 1 — answer is 2.
  • Very large coin values — the gap is detected early if small denominations are missing.

Linked mentions