Minimum Shopping Cost with Vouchers

Overview

The goal is to reduce the total cost of $n$ products by applying vouchersCount vouchers. Each voucher halves the price of an item ($\lfloor p / 2 \rfloor$). Since we want to minimize the sum of the final prices, the most effective use of a voucher is always on the item that currently has the highest price. By reducing the largest value in the list, we maximize the absolute reduction in cost for that step. This greedy strategy must be repeated until all vouchers are exhausted or all prices become zero.

Brute Force

In a brute-force approach, for every single voucher, we scan the entire list of prices to find the maximum value, apply the voucher to it, and update the list. We repeat this process vouchersCount times.

def min_shopping_cost(prices: list[int], vouchersCount: int) -> int:
    # Make a copy to avoid modifying the input
    current_prices = list(prices)
    
    for _ in range(vouchersCount):
        # Find the index of the current maximum price
        max_idx = 0
        for i in range(1, len(current_prices)):
            if current_prices[i] > current_prices[max_idx]:
                max_idx = i
        
        # If the max price is already 0, we can't reduce further
        if current_prices[max_idx] == 0:
            break
            
        # Apply the voucher
        current_prices[max_idx] //= 2
        
    return sum(current_prices)

Time complexity: O(vouchersCount * n) — We iterate through the list of size $n$ to find the maximum element for every one of the $k$ vouchers. Space complexity: O(n) — We store the prices in a list of size $n$.

Optimal Approach

To improve efficiency, we need a faster way to retrieve and update the maximum element. A Max-Heap (Priority Queue) is ideal for this. In Python, the heapq module implements a Min-Heap by default, so we can simulate a Max-Heap by storing all prices as negative values.

1. Push all prices into a Max-Heap.
2. While vouchersCount > 0, extract the largest price $p$.
3. If $p = 0$, stop (no further reductions possible).
4. Apply the voucher: $p = \lfloor p / 2 \rfloor$.
5. Push the updated price back into the heap and decrement vouchersCount.
6. The result is the sum of all elements remaining in the heap.

import heapq

def min_shopping_cost(prices: list[int], vouchersCount: int) -> int:
    # Use negative values to simulate a Max-Heap using Python's heapq (Min-Heap)
    max_heap = [-p for p in prices]
    heapq.heapify(max_heap)
    
    while vouchersCount > 0 and max_heap:
        # Get the largest element (most negative)
        highest = -heapq.heappop(max_heap)
        
        if highest == 0:
            break
            
        # Apply voucher and push back
        new_price = highest // 2
        heapq.heappush(max_heap, -new_price)
        vouchersCount -= 1
        
    return -sum(max_heap)

Time complexity: O(n + vouchersCount * log n) — Building the heap takes $O(n)$. Each voucher application involves a pop and push operation, each taking $O(\log n)$. Space complexity: O(n) — We store $n$ elements in the heap.

Why this works

The greedy choice property holds here because the function $f(x) = \lfloor x/2 \rfloor$ is monotonic, and the reduction $x - \lfloor x/2 \rfloor$ is non-decreasing with respect to $x$. In other words, applying a voucher to a larger number always yields a reduction (savings) greater than or equal to applying it to a smaller number. By consistently picking the largest available price, we ensure that each individual voucher provides the maximum possible discount at that moment.

Fast