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)); 

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)