Katkat
Back

Minimize coins with overpay and change

SnowflakeSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to optimize combinatorial decisions under constraints by identifying a greedy approach with a fallback to search or dynamic programming.

Problem Statement

You are tasked with paying exactly target amount using a set of coin denominations coins. However, the store has a specific policy: you can provide a larger amount P (where P > target), and the store will return the difference P - target as change using the same available denominations.

You want to minimize the total number of coins handled (the sum of coins you provide plus the coins the store returns as change). If it is impossible to pay the exact amount or make the change using the given denominations, return -1.

Function Signature

def min_total_coins(coins: List[int], target: int) -> int:

Constraints

  • 1 <= target <= 10,000
  • 1 <= len(coins) <= 20
  • 1 <= coins[i] <= 1,000
  • You may assume that the maximum overpay needed is at most target + max(coins).

Examples

Example 1:

  • coins = [1, 5, 10], target = 3
  • Providing 5: You give one 5-coin, store returns two 1-coins. Total = 3 coins.
  • Providing 3: You give three 1-coins, store returns zero. Total = 3 coins.
  • Output: 3

Example 2:

  • coins = [2, 5], target = 3
  • Providing 5: You give one 5-coin, store returns one 2-coin. Total = 2 coins.
  • Output: 2

Edge Cases

  • If target can be formed directly with the fewest coins, consider if adding a coin and receiving change could result in a smaller total count.

Hints

Hint 1

First, compute the minimum number of coins to form every value up to a reasonable upper bound using standard dynamic programming (the coin change problem).

Hint 2

Define a search space where you choose to pay `P` (where `target <= P <= target + max(coins)`) and represent the total cost as `min_coins(P) + min_coins(P - target)`.

Hint 3

Ensure your DP array is large enough to accommodate the maximum possible payment amount, which should be slightly greater than the target to allow for change.

Follow-up questions

  • How does the time complexity change if we remove the upper bound on the amount `P` you can pay?
  • If the denominations were not static but changed daily, what data structure would you use to store the precomputed minimum coin counts efficiently?
  • What if the store charges a flat 'transaction fee' for every coin handled in the return change process?