Most Expensive Item That Can Not Be Bought

Medium

Amazon

3 views

Topics:

Dynamic Programming

You are given a set of item prices. You can buy any number of these items. Find the largest amount of money that cannot be formed using combinations of these prices.

In other words, given a set of positive integers, find the largest integer that cannot be expressed as a non-negative integer linear combination of the elements of the set.

Example 1:

Input: prices = [2, 3]
Output: 1
Explanation: 
We can form:
2, 3, 4, 5, 6, 7, 8, 9, 10, ...
We can form any number greater than 1.

Example 2:

Input: prices = [3, 5, 7]
Output: 4
Explanation:
We can form:
3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, ...
We can form any number greater than 4.

Example 3:

Input: prices = [1, 5, 10]
Output: 0
Explanation: 
We can form any positive integer.  Since we can buy an item of price 1, we can form any amount. Thus, the largest amount that cannot be formed is 0.

Constraints:

1 <= prices.length <= 10
1 <= prices[i] <= 100
The greatest common divisor (GCD) of the prices is 1. This ensures that there exists a largest unrepresentable number.

Try coding it in LeetCode

Most Expensive Item That Can Not Be Bought

Medium

Amazon

3 views

Topics:

Dynamic Programming

You are given a set of item prices. You can buy any number of these items. Find the largest amount of money that cannot be formed using combinations of these prices.

In other words, given a set of positive integers, find the largest integer that cannot be expressed as a non-negative integer linear combination of the elements of the set.

Example 1:

Input: prices = [2, 3]
Output: 1
Explanation: 
We can form:
2, 3, 4, 5, 6, 7, 8, 9, 10, ...
We can form any number greater than 1.

Example 2:

Input: prices = [3, 5, 7]
Output: 4
Explanation:
We can form:
3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, ...
We can form any number greater than 4.

Example 3:

Input: prices = [1, 5, 10]
Output: 0
Explanation: 
We can form any positive integer.  Since we can buy an item of price 1, we can form any amount. Thus, the largest amount that cannot be formed is 0.

Constraints:

1 <= prices.length <= 10
1 <= prices[i] <= 100
The greatest common divisor (GCD) of the prices is 1. This ensures that there exists a largest unrepresentable number.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible values for the cost of each item?
Can the array of item costs be empty, or contain zero or negative values?
If no item can be bought given the current constraints, what value should I return?
Are the item costs integers, or could they be floating point numbers?
Can I assume I have enough money to buy at least the cheapest item, or is it possible I can't afford anything?

Brute Force Solution

Approach

The brute force approach to finding the most expensive item that cannot be bought involves checking every single possible price. We systematically test each price to see if it can be formed by combining the prices of available items.

Here's how the algorithm would work step-by-step:

Start with a price of 1, then 2, then 3, and so on, going up one at a time.
For each price, try all the possible combinations of available item prices to see if they add up to that price exactly.
If you find a combination that adds up to the price, then that price *can* be bought, so move on to the next price.
If you try every single combination of items and *none* of them add up to the price, then that price *cannot* be bought.
Keep checking prices until you find a very large price that *can* be bought. At this point, we can assume that all higher prices can also be bought using combinations of the available items.
The most expensive price that cannot be bought is the largest price you encountered before finding a long string of prices that *can* be bought.

Code Implementation

def find_most_expensive_unbuyable_item(item_prices):
    most_expensive_unbuyable = 0
    consecutive_buyable_count = 0
    max_consecutive_buyable = 100 # Threshold for assuming all higher prices are buyable

    current_price = 1
    while consecutive_buyable_count < max_consecutive_buyable:
        is_buyable = False
        
        # Check if the current price can be formed by combinations of item prices
        for i in range(2**(len(item_prices))):
            combination_sum = 0
            for j in range(len(item_prices)):
                if (i >> j) & 1:
                    combination_sum += item_prices[j]

            if combination_sum == current_price:
                is_buyable = True
                break

        if is_buyable:
            consecutive_buyable_count += 1
        else:
            # Update the most expensive unbuyable item if current price is not buyable
            most_expensive_unbuyable = current_price
            consecutive_buyable_count = 0
        
        current_price += 1

    return most_expensive_unbuyable

Big(O) Analysis

Time Complexity

O(m * a^n) – Let 'm' be the maximum price we check until we find a long sequence of possible prices, 'n' be the number of available item prices, and 'a' represent the average number of possible combinations we need to try for each price. For each price from 1 to 'm', we explore combinations of the 'n' item prices, resulting in a trials which is exponential with 'n'. Therefore, the overall time complexity is approximately O(m * a^n), as we iterate up to m and try combinations for each. Note: 'a' is related to number of subsets that can be made from n, but since we don't have the restriction that each subset must have a unique length, it can be greater than power set size of n if subsets can have repeating length. The precise value of 'a' depends on the specific combination-generating algorithm and the input item prices.

Space Complexity

O(1) – The brute force approach, as described, iterates through potential prices and checks combinations. It does not explicitly mention or imply the use of auxiliary data structures like arrays, hash maps, or significant recursion. The space complexity is primarily determined by the variables used to track the current price being checked and potentially a few other temporary variables used in the combination checking process, which are constant regardless of the input items. Thus, the auxiliary space used remains constant irrespective of the number of items, N, and simplifies to O(1).

Optimal Solution

Approach

The problem asks us to find the largest value that cannot be created by combining a given set of item prices. We will use a mathematical trick to find a point where all numbers above it can be made, and therefore the solution is the largest number below it that can't.

Here's how the algorithm would work step-by-step:

First, find the smallest of all the item prices. Let's call that value 'minimum'.
Check if minimum is equal to 1. If it is, then every price can be made so the answer is -1, which means no such number exists.
Create a method for checking if a particular total price can be made using the given set of item prices. Do this by trying to subtract item prices repeatedly.
Start checking total prices backwards from minimum times the largest item price. It may seem arbitrary but will give the algorithm the best speed.
If we find a certain number of consecutive prices, each separated by 1, that *can* be made with the available items, then we know every price higher than those prices can also be made.
The lowest of those consecutive numbers is our 'tipping point'.
Once we reach the tipping point, the solution is simply the number 1 smaller than our consecutive number.
If after trying all numbers backwards to 0 we haven't found a tipping point, then the answer is more complex. However, for all valid test cases, a solution will have been found using the approach in previous steps.

Code Implementation

def most_expensive_item_that_cannot_be_bought(item_prices):
    minimum_price = min(item_prices)

    if minimum_price == 1:
        return -1

    def can_make_price(target_price, available_prices):
        if target_price == 0:
            return True
        if target_price < 0:
            return False

        for price in available_prices:
            if can_make_price(target_price - price, available_prices):
                return True
        return False

    # Start checking downwards from a reasonable upper bound.
    start_price = minimum_price * max(item_prices)
    consecutive_prices_that_can_be_made = 0
    consecutive_prices_needed = minimum_price

    for current_price in range(start_price, -1, -1):
        if can_make_price(current_price, item_prices):
            consecutive_prices_that_can_be_made += 1

            # If we have reached the tipping point.
            if consecutive_prices_that_can_be_made == consecutive_prices_needed:

                # This is the number one less than the lowest consecutive value.
                return current_price - 1
        else:
            # Reset the counter if the current price cannot be made.
            consecutive_prices_that_can_be_made = 0

    # If no solution is found, return -1 as a failsafe.
    return -1

Big(O) Analysis

Time Complexity

O(n*m*k) – The dominant factor in the runtime is the loop that checks prices backwards from minimum times the largest item price. 'n' represents the number of item prices. The 'm' represents the largest item price times the smallest item price, dictating the upper bound of the price range checked. Inside this loop, a method is called to check if a particular price can be made. This method, in the worst case, might iterate through all item prices 'k' multiple times, potentially subtracting prices to reach zero or a negative value, creating a nested loop. Therefore, the approximate total operations are proportional to n*m*k which simplifies to O(n*m*k).

Space Complexity

O(N) – The primary space complexity stems from the 'checking if a particular total price can be made' method. This method, in the worst case, might use a recursion stack to a depth proportional to the target 'total price'. The problem explanation mentions iterating backwards from 'minimum times the largest item price', implying the largest item price plays a significant role in determining this recursion depth, and therefore the stack space. Consequently, auxiliary space can be considered proportional to the magnitude of the item prices, implying a dependency on the number of item prices N. Therefore, the overall space complexity is O(N) where N is related to the number and values of the prices.

Edge Cases

Case	How to Handle
Empty 'costs' array	Return 0, as no items are available, making it impossible to buy anything
All costs are zero	Return 0, as no matter how much you have you can't buy anything, as if you can buy everything nothing will be left over
All costs are the same positive value	Return the given money modulo the cost, since the only value left is whatever is less than the cost
Money is zero	Return 0, as you can't buy anything with no money
Costs contain negative numbers	Treat negative costs as if they were free, buy as many of those as possible and ignore them for the calculation of leftovers since those are effectively free
Costs are very large numbers (potential overflow)	Use a long or similar data type to avoid integer overflow when summing costs if a summation is necessary
Only one item, and money is less than the cost of that item	Return the amount of money available since nothing can be bought
The maximum cost is significantly higher than the other costs	The solution should efficiently handle this skewed distribution by prioritizing purchasing items with lower costs