Minimum Coins

13
0

Problem Statement

An array coins containing distinct positive coin denominations and a non-negative integer amount are given. Every denomination may be selected any number of times.

Return the minimum number of coins having a total value equal to amount. Return -1 after no exact combination can form the target. A target amount of 0 requires no coins and returns 0.

Example 1

Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: Coins [5, 5, 1] form 11 with three coins, and no two available coins can form 11.

Example 2

Input: coins = [2, 5], amount = 3
Output: -1
Explanation: Repeated values 2 and 5 cannot produce an exact total of 3.

Recursion

Each denomination creates a simple choice. Skipping the current denomination moves to smaller denominations, while taking the current denomination reduces the remaining amount and keeps the same denomination available. Keeping the same index after a take captures the unlimited supply rule.

State solve(index, remaining) returns the fewest coins needed from denominations 0 through index. The initial call uses (n - 1, amount) because the full denomination list and complete target must remain available at the beginning.

Algorithm

  • Begin with state (n - 1, amount) because the complete denomination list must build the original target.

  • Handle index 0 through divisibility because repeated copies of the first denomination provide the only remaining possible construction.

  • Explore the skip branch with (index - 1, remaining) because excluding the current denomination leaves the required amount unchanged.

  • Keep the take branch at infinity until the current denomination fits because an oversized coin cannot belong to an exact positive remainder.

  • Explore the take branch with (index, remaining - coins[index]) because unlimited supply keeps the current denomination available.

  • Add one only after the smaller take state is valid because an impossible remainder must never become a valid candidate.

  • Return the smaller branch count because the required combination uses the fewest coins among every valid pick-or-skip path.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
int infinity = 1000000000;
// Finds the minimum count for one DP state.
int solve(
int index,
int remaining,
vector<int>& coins
) {
// The first coin must divide the remainder.
if (index == 0) {
// Exact division creates a valid construction.
if (remaining % coins[0] == 0) {
return remaining / coins[0];
}
return infinity;
}
// Skipping moves to smaller denominations.
int notTaken = solve(index - 1, remaining, coins);
int taken = infinity;
// Taking is valid only inside the remainder.
if (coins[index] <= remaining) {
// Reuse keeps the current index available.
int smaller = solve(
index,
remaining - coins[index],
coins
);
// Only a valid smaller state accepts a coin.
if (smaller != infinity) {
taken = 1 + smaller;
}
}
// The smaller count gives the best construction.
return min(notTaken, taken);
}
public:
// Returns the minimum coins for the target.
int minimumCoins(vector<int>& coins, int amount) {
int n = coins.size();
// The full list starts with the full target.
int answer = solve(n - 1, amount, coins);
// The sentinel marks an impossible target.
if (answer == infinity) {
return -1;
}
return answer;
}
};
// Driver code
int main() {
vector<int> coins = {1, 2, 5};
int amount = 11;
Solution obj;
cout << obj.minimumCoins(coins, amount);
return 0;
}

Note: Direct recursion may fail for large input values. Repeated subproblems create exponential work, so an online judge may report Time Limit Exceeded.

Complexity Analysis

Time Complexity: O(2(N + amount / minCoin)), where N is the number of denominations, because each state can branch into skip and take choices across at most N + amount / minCoin recursive levels. Here, minCoin denotes the smallest denomination.

Space Complexity: O(N + amount / minCoin), because the deepest recursion path can contain denomination skips and repeated takes before reaching a base state. Here, minCoin denotes the smallest denomination.

Memoization

Many recursive paths reach the same pair of index and remaining amount. A dp table stores each completed state, so later visits can reuse an answer instead of rebuilding the same recursion tree.

State meaning and branch logic remain unchanged. Only a cache check before recursion and a cache write after the minimum calculation are added.

Algorithm

  • Begin with a dp table of size n by amount + 1, filled with -1, so every untouched cell marks an uncalculated state.

  • Start from (n - 1, amount) because the complete denomination list must still form the full target.

  • Handle index 0 through divisibility because only repeated copies of the first denomination remain available.

  • Return dp[index][remaining] after a cache hit because the same state always has the same minimum count.

  • Explore the unchanged skip and take branches because memoization must preserve the recursive state meaning.

  • Store the smaller valid branch count in dp because later paths can avoid rebuilding the same state.

  • Convert the infinity sentinel to -1 at the public boundary because the required output uses -1 for an impossible target.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
int infinity = 1000000000;
// Finds and stores one minimum-count state.
int solve(
int index,
int remaining,
vector<int>& coins,
vector<vector<int>>& dp
) {
// The first coin must divide the remainder.
if (index == 0) {
// Exact division creates a valid construction.
if (remaining % coins[0] == 0) {
return remaining / coins[0];
}
return infinity;
}
// A stored state avoids repeated recursion.
if (dp[index][remaining] != -1) {
return dp[index][remaining];
}
// Skipping moves to smaller denominations.
int notTaken = solve(
index - 1,
remaining,
coins,
dp
);
int taken = infinity;
// Taking is valid only inside the remainder.
if (coins[index] <= remaining) {
// Reuse keeps the current index available.
int smaller = solve(
index,
remaining - coins[index],
coins,
dp
);
// Only a valid smaller state accepts a coin.
if (smaller != infinity) {
taken = 1 + smaller;
}
}
// The cache stores the smaller branch count.
dp[index][remaining] = min(notTaken, taken);
return dp[index][remaining];
}
public:
// Returns the minimum coins for the target.
int minimumCoins(vector<int>& coins, int amount) {
int n = coins.size();
// Negative one marks every uncalculated state.
vector<vector<int>> dp(
n,
vector<int>(amount + 1, -1)
);
// The full list starts with the full target.
int answer = solve(
n - 1,
amount,
coins,
dp
);
// The sentinel marks an impossible target.
if (answer == infinity) {
return -1;
}
return answer;
}
};
// Driver code
int main() {
vector<int> coins = {1, 2, 5};
int amount = 11;
Solution obj;
cout << obj.minimumCoins(coins, amount);
return 0;
}

Complexity Analysis

Time Complexity: O(N × amount), where N is the number of denominations, because at most N × (amount + 1) states are calculated once, with constant-time skip, take, and minimum operations per state.

Space Complexity: O(N × amount + N + amount / minCoin), because the dp table stores all states, while the recursion stack can grow through skipped denominations and repeated takes of the smallest denomination. Here, minCoin denotes the smallest denomination.

Tabulation

Tabulation evaluates the same states from smaller indices and smaller amounts upward. The first row handles repeated copies of the first denomination, and every later row compares skipping the current coin with taking the current coin again.

An increasing amount order keeps dp[index][value - coins[index]] ready inside the current row. The current-row reference preserves unlimited reuse, while the previous-row reference represents a skip.

Algorithm

  • Begin with an n by amount + 1 table filled with infinity so unreachable sums cannot win a minimum comparison.

  • Fill the first row through divisibility because only repeated copies of coins[0] can form first-row amounts.

  • Process denomination rows from index 1 upward because every skip transition needs the completed previous row.

  • Process amounts from 0 through amount because every take transition needs a smaller amount from the current row.

  • Read dp[index - 1][value] for the skip count because excluding the current denomination moves to the preceding row.

  • Read dp[index][value - coins[index]] for a valid take because unlimited supply keeps the current row active.

  • Store the smaller branch count and convert the final infinity value to -1 because only exact constructions qualify.

Dry Run

Minimum Coin Tabulation

Minimum Coin Tabulation

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns the minimum coins for the target.
int minimumCoins(vector<int>& coins, int amount) {
int n = coins.size();
int infinity = 1000000000;
// Infinity marks every unreachable state.
vector<vector<int>> dp(
n,
vector<int>(amount + 1, infinity)
);
// Divisible amounts use only the first coin.
for (int value = 0; value <= amount; value++) {
// Exact division creates a valid construction.
if (value % coins[0] == 0) {
dp[0][value] = value / coins[0];
}
}
// Each row adds one available denomination.
for (int index = 1; index < n; index++) {
// Ascending amounts allow current-coin reuse.
for (int value = 0; value <= amount; value++) {
// The previous row represents a skip.
int notTaken = dp[index - 1][value];
int taken = infinity;
// Taking is valid only inside the amount.
if (coins[index] <= value) {
int smaller = dp[
index
][value - coins[index]];
// Only a valid smaller state accepts a coin.
if (smaller != infinity) {
taken = 1 + smaller;
}
}
// Both branch counts define the current state.
dp[index][value] = min(
notTaken,
taken
);
}
}
int answer = dp[n - 1][amount];
// The sentinel marks an impossible target.
if (answer == infinity) {
return -1;
}
return answer;
}
};
// Driver code
int main() {
vector<int> coins = {1, 2, 5};
int amount = 11;
Solution obj;
cout << obj.minimumCoins(coins, amount);
return 0;
}

Complexity Analysis

Time Complexity: O(N × amount), where N is the number of denominations, because every row processes all amount + 1 target values once.

Space Complexity: O(N × amount), because the two-dimensional dp table stores one minimum count for every denomination-and-amount state, with no recursion stack.

Space Optimization

Each tabulation state reads a skip value from the previous row and a smaller take value from the current row. Rows older than the previous row never contribute to a new state, so the full table can shrink to two arrays.

Array previous represents the completed row before the current denomination. Array current is calculated from left to right, then the completed current row becomes previous for the next denomination.

Algorithm

  • Begin with previous filled with infinity so unreachable amounts remain excluded from minimum comparisons.

  • Fill previous through divisibility because the first denomination alone defines the first conceptual DP row.

  • Create a fresh current row for every later denomination so stale values cannot leak across denomination states.

  • Process amounts in increasing order because taking the current denomination reads an already calculated smaller amount from current.

  • Compare previous[value] with 1 + current[value - coins[index]] because the two values represent skipping and taking the denomination.

  • Store the minimum in current[value], then assign the completed row to previous because the next denomination needs only the newest results.

  • Return previous[amount] or -1 after the sentinel remains because the final rolling row represents the complete denomination list.

Dry Run

Minimum Coin Space Optimizaiton

Minimum Coin Space Optimizaiton

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns the minimum coins for the target.
int minimumCoins(vector<int>& coins, int amount) {
int n = coins.size();
int infinity = 1000000000;
// Infinity marks unreachable first-row amounts.
vector<int> previous(amount + 1, infinity);
// Divisible amounts use only the first coin.
for (int value = 0; value <= amount; value++) {
// Exact division creates a valid construction.
if (value % coins[0] == 0) {
previous[value] = value / coins[0];
}
}
// Each pass builds the next denomination row.
for (int index = 1; index < n; index++) {
vector<int> current(amount + 1, infinity);
// Ascending amounts allow current-coin reuse.
for (int value = 0; value <= amount; value++) {
// The previous row represents a skip.
int notTaken = previous[value];
int taken = infinity;
// Taking is valid only inside the amount.
if (coins[index] <= value) {
int smaller = current[
value - coins[index]
];
// A valid smaller state accepts a coin.
if (smaller != infinity) {
taken = 1 + smaller;
}
}
// Current keeps the best of both choices.
current[value] = min(notTaken, taken);
}
// Shift the finished row into previous.
previous.swap(current);
}
int answer = previous[amount];
// The sentinel marks an impossible target.
if (answer == infinity) {
return -1;
}
return answer;
}
};
// Driver code
int main() {
vector<int> coins = {1, 2, 5};
int amount = 11;
Solution obj;
cout << obj.minimumCoins(coins, amount);
return 0;
}

Complexity Analysis

Time Complexity: O(N × amount), where N is the number of denominations, because every denomination processes all amount + 1 target values once.

Space Complexity: O(amount), because only the previous and current arrays of length amount + 1 are kept in memory.

Interview follow-up Questions

No. For coins = [1, 3, 4] and amount = 6, greedy selection uses [4, 1, 1], while optimal selection uses [3, 3].

Dynamic ProgrammingTCS NQT

Read Similar Blogs

Comments0