The Most Expensive Item That Cannot Be Bought

Problem

Given a set of coin denominations, what is the largest amount that cannot be obtained using any combination of coins in the set?

For example, if the coin denominations are {3, 5}, then the largest amount that cannot be obtained is 7.

Naive Solution

A brute-force approach would be to iterate through every possible amount, starting from 1, and check if that amount can be formed using the given denominations. We can stop when we find an amount that cannot be formed and is larger than any previously found unformable amount.

Code

def can_be_formed(amount, denominations):
    if amount == 0:
        return True
    if amount < 0:
        return False

    for coin in denominations:
        if can_be_formed(amount - coin, denominations):
            return True
    return False

def largest_unformable(denominations):
    i = 1
    largest = 0
    while i < 100: # Added upper bound to avoid infinite loops
        if not can_be_formed(i, denominations):
            largest = i
        i += 1
    return largest

Time Complexity

Exponential, since the can_be_formed function recurses, branching out depending on the number of denominations and the target amount.

Space Complexity

O(amount) due to the recursion depth.

Edge Cases

• If the denominations contain 1, then every amount can be formed, so the result is 0. The code above will not work without the limit of 100, and will infinitely recurse. The efficient solution handles this.
• Empty denominations: If the input denominations array is empty, then it's not possible to form any positive amount. In this case, there is no largest amount that cannot be formed. We could say the answer is infinity, but since that is not programmatically possible, return -1 to signify that there is no such largest value.

Optimal Solution

This problem can be solved with dynamic programming. The algorithm involves creating a boolean array, dp, where dp[i] is true if the amount i can be formed using the given denominations, and false otherwise. The largest unformable amount would be the highest index i such that dp[i] is false.

Algorithm

1. Find an upper bound for the maximum possible unformable amount. According to the Chicken McNugget Theorem, if we have two relatively prime denominations a and b, then the largest amount that cannot be formed is (a * b) - a - b. We can generalize this upper bound as n * max(denominations) where n is the number of denominations. We can choose some sufficiently large n. It's better to overshoot than undershoot because we may give the wrong result if we undershoot the true maximum unformable amount. If the denominations are not co-prime, this formula still gives a valid (but potentially non-tight) upper bound.
2. Initialize a boolean array dp of size upper_bound + 1 to all False. Set dp[0] to True (base case: amount 0 can be formed).
3. Iterate through amounts from 1 to upper_bound. For each amount i, iterate through each coin denomination coin. If i >= coin and dp[i - coin] is true, then dp[i] is also true.
4. Iterate through the dp array from the end. Find the first i for which dp[i] is false. This is the largest unformable amount.

Code

def largest_unformable_dp(denominations):
    if 1 in denominations:
        return 0
    
    if not denominations:
        return -1

    upper_bound = len(denominations) * max(denominations)
    dp = [False] * (upper_bound + 1)
    dp[0] = True

    for i in range(1, upper_bound + 1):
        for coin in denominations:
            if i >= coin and dp[i - coin]:
                dp[i] = True
                break

    for i in range(upper_bound, -1, -1):
        if not dp[i]:
            return i

    return 0 # Should ideally not reach here

Time Complexity

O(n * m), where n is the upper bound (approximately len(denominations) * max(denominations)) and m is the number of denominations.

Space Complexity

O(n), where n is the upper bound. This is due to the size of the dp array.

Edge Cases

• If the denominations contain 1, then every amount can be formed, so the result is 0.
• Empty denominations: If the input denominations array is empty, then it's not possible to form any positive amount. In this case, there is no largest amount that cannot be formed. We return -1 to indicate that there is no such largest value.
• Denominations are all the same number, example: [2, 2, 2]. In this case, the largest unformable number would be 1.