advanced

Review: the change maker that settles for more

This is recall. The code looks finished and is wrong. Find the defect and fix it. You are graded on tests you cannot see.

The change routine came back from a code generator as a tidy greedy: walk the coins biggest first, take as many as fit, move on. On the coin systems in its tests — US denominations, mostly — it produces the provably best answer, because those systems are built to make greedy optimal.

/**
 * Returns the minimum number of coins summing exactly to `amount`, or -1
 * when no combination of `coins` reaches it.
 */
export function fewestCoins(coins: number[], amount: number): number {
  let remaining = amount
  let used = 0

  const sorted = [...coins].sort((a, b) => b - a)
  for (const coin of sorted) {
    while (remaining >= coin) {
      remaining -= coin
      used += 1
    }
  }

  return remaining === 0 ? used : -1
}

review — find the defectCtrl+↵ submits · Ctrl+Shift+↵ runsstarter code