Fewest coins

Challenge

Implement:

int min_coins(const int *coins, int nc, int amount);

Return the fewest coins (unlimited supply of each) that sum exactly to amount, or -1 if impossible.

Input format

coins (positive), nc, and a non-negative amount.

Output format

Fewest coins, or -1.

Constraints

amount up to ~10000.

Starter code

#include <stddef.h>
/* Fewest coins that sum to amount using coins[0..nc-1] (unlimited each); -1 if impossible. amount>=0, coins positive. */
int min_coins(const int *coins,int nc,int amount){ (void)coins;(void)nc;(void)amount; return -1; }

Common mistakes

Greedy fails for arbitrary denominations — you need DP over every amount.

Edge cases to handle

amount 0 needs 0 coins; unreachable amounts return -1.

Background lessons

• Coin change