CSES Solutions – Minimizing Coins
Consider a money system consisting of N coins. Each coin has a positive integer value. Your task is to produce a sum of money X using the available coins in such a way that the number of coins is minimal.
Examples:
Input: N = 3, X = 11, coins[] = {1, 5, 7}
Output: 3
Explanation: We need minimum 3 coins to make the sum 11, 5 + 5 + 1 = 11.Input: N = 3, X = 6, coins[] = {1, 2, 3}
Output: 2
Explanation: We need 2 coins to make sum = 6, 3 + 3 = 6.
Approach: To solve the problem, follow the below idea:
The problem can be solved using Dynamic Programming. We can maintain a dp[] array, such that dp[i] stores the minimum number of coins needed to make sum = i. We can iterate i from 1 to X, and find the minimum number of coins to make sum = i. For any sum i, we assume that the last coin used was the jth coin where j will range from 0 to N – 1. For jth coin, the value will be coins[j], so the minimum number of coins to make sum as i if the last coin used was the jth coin = dp[i – coins[j]] + 1. The formula for the ith sum will be: dp[i] = min(dp[i], dp[i – coins[j]] + 1), for all j from 0 to N – 1
Also, the above formula will be true only when coins[j] >= i and it is possible to make sum = i – coins[j].
Step-by-step algorithm:
- Maintain a dp[] array, such that dp[i] stores the minimum number of coins to make sum = i.
- Initialize dp[0] = 0 as 0 coins are required to make sum = 0.
- Iterate i from 1 to X and calculate minimum number of coins to make sum = i.
- Iterate j over all possible coins assuming the jth coin to be last coin which was selected to make sum = i and update dp[i] with dp[i – coins[j]] + 1 if dp[i – coins[j]] + 1 < dp[i].
- After all the iterations, return the final answer as dp[X].
Below is the implementation of the algorithm:
#include <bits/stdc++.h>
#define ll long long int
#define INF 1000000000
using namespace std;
// Function to find the minimum number of coins to make
// sum X
ll solve(ll N, ll X, vector<ll>& coins)
{
// dp[] array such that dp[i] stores the minimum number
// of coins to make sum = i
vector<ll> dp(X + 1, INF);
dp[0] = 0;
// Iterate over all possible sums from 1 to X
for (int i = 1; i <= X; i++) {
// Iterate over all coins
for (int j = 0; j < N; j++) {
if (coins[j] > i || dp[i - coins[j]] == INF)
continue;
dp[i] = min(dp[i], dp[i - coins[j]] + 1);
}
}
// If it is possible to make sum = X, return dp[X]
if (dp[X] != INF)
return dp[X];
// If it is impossible to make sum = X, return -1
return -1;
}
int main()
{
// Sample Input
ll N = 3, X = 6;
vector<ll> coins = { 1, 2, 3 };
cout << solve(N, X, coins) << "\n";
}
import java.util.*;
public class MinCoinsToMakeSum {
static final int INF = 1000000000;
// Function to find the minimum number of coins to make sum X
static long solve(int N, int X, List<Integer> coins) {
// dp[] array such that dp[i] stores the minimum number
// of coins to make sum = i
long[] dp = new long[X + 1];
Arrays.fill(dp, INF);
dp[0] = 0;
// Iterate over all possible sums from 1 to X
for (int i = 1; i <= X; i++) {
// Iterate over all coins
for (int j = 0; j < N; j++) {
if (coins.get(j) > i || dp[i - coins.get(j)] == INF) {
continue;
}
dp[i] = Math.min(dp[i], dp[i - coins.get(j)] + 1);
}
}
// If it is possible to make sum = X, return dp[X]
if (dp[X] != INF) {
return dp[X];
}
// If it is impossible to make sum = X, return -1
return -1;
}
public static void main(String[] args) {
// Sample Input
int N = 3, X = 6;
List<Integer> coins = Arrays.asList(1, 2, 3);
System.out.println(solve(N, X, coins));
}
}
// This code is contributed by shivamgupta0987654321
# Function to find the minimum number of coins to make
# sum X
def solve(N, X, coins):
# dp[] array such that dp[i] stores the minimum number
# of coins to make sum = i
dp = [float('inf')] * (X + 1)
dp[0] = 0
# Iterate over all possible sums from 1 to X
for i in range(1, X + 1):
# Iterate over all coins
for j in range(N):
if coins[j] > i or dp[i - coins[j]] == float('inf'):
continue
dp[i] = min(dp[i], dp[i - coins[j]] + 1)
# If it is possible to make sum = X, return dp[X]
if dp[X] != float('inf'):
return dp[X]
# If it is impossible to make sum = X, return -1
return -1
# Sample Input
N = 3
X = 6
coins = [1, 2, 3]
print(solve(N, X, coins))
using System;
public class MinimumCoins
{
// Function to find the minimum number of coins to make sum X
public static int Solve(int N, int X, int[] coins)
{
// dp[] array such that dp[i] stores the minimum number
// of coins to make sum = i
int[] dp = new int[X + 1];
Array.Fill(dp, int.MaxValue);
dp[0] = 0;
// Iterate over all possible sums from 1 to X
for (int i = 1; i <= X; i++)
{
// Iterate over all coins
for (int j = 0; j < N; j++)
{
if (coins[j] > i || dp[i - coins[j]] == int.MaxValue)
continue;
dp[i] = Math.Min(dp[i], dp[i - coins[j]] + 1);
}
}
// If it is possible to make sum = X, return dp[X]
if (dp[X] != int.MaxValue)
return dp[X];
// If it is impossible to make sum = X, return -1
return -1;
}
public static void Main(string[] args)
{
// Sample Input
int N = 3;
int X = 6;
int[] coins = new int[] { 1, 2, 3 };
Console.WriteLine(Solve(N, X, coins));
}
}
// Function to find the minimum number of coins to make sum X
function solve(N, X, coins) {
// dp[] array such that dp[i] stores the minimum number
// of coins to make sum = i
let dp = new Array(X + 1).fill(Number.MAX_SAFE_INTEGER);
dp[0] = 0;
// Iterate over all possible sums from 1 to X
for (let i = 1; i <= X; i++) {
// Iterate over all coins
for (let j = 0; j < N; j++) {
if (coins[j] > i || dp[i - coins[j]] === Number.MAX_SAFE_INTEGER)
continue;
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
// If it is possible to make sum = X, return dp[X]
if (dp[X] !== Number.MAX_SAFE_INTEGER)
return dp[X];
// If it is impossible to make sum = X, return -1
return -1;
}
// Sample Input
let N = 3, X = 6;
let coins = [1, 2, 3];
console.log(solve(N, X, coins));
Output
2
Time Complexity: O(N * X), where N is the number of coins and X is the sum of coins we want to make.
Auxiliary Space: O(X)
Contact Us