﻿ Find Minimum Numbers of Currency for Required Amount - ITCodar

# Find Minimum Numbers of Currency for Required Amount

## Find minimum number of currency notes and values that sum to given amount array issue

To convert float number of notes to integer use `Math.trunc` or `Math.floor`: `Math.trunc(remaining / note)`

The whole code can look like:

``function findNoteAndCoins(salary) {  const notes = [5000, 1000, 500, 100, 50, 20, 10, 5, 2, 1];  const notesCount = [];  let remaining = salary;  for (const note of notes) {    if (salary >= note) {      notesCount.push(Math.trunc(remaining / note));      remaining = remaining % note;    } else {      notesCount.push(0);    }  }  return notesCount;}console.log(findNoteAndCoins(2316));``

and we can check that the `findNoteAndCoins` function works:

``function findSalary(notesCount) {  const notes = [5000, 1000, 500, 100, 50, 20, 10, 5, 2, 1];  let salary = 0;  for (let i = 0; i < notesCount.length; i++) {    salary += notesCount[i] * notes[i];  }  return salary;}console.log(findSalary(findNoteAndCoins(2316)) === 2316);``

## Finding minimum number of notes to make a amount

The error in the algorithm is in the order of two lines that should be the other way around:

``least_notes+=n//p n=n-(p*n//p) #rest amount of money ``

since the `least_notes` count should be increased before `n` is updated recursively.

## Calculate the Minimum Number of Coins For Given Amount of Change in Haskell

In this answer I will focus on this attempt of yours:

``coinChange c [] = []coinChange c ds =reverse( (c `quot` x):(coinChange' (c `rem` x) xs ))                where (x:xs) = (reverse ds)coinChange' c [] = []coinChange' c ds = (c`quot`x):(coinChange' (c `rem` x) xs )                where (x:xs) = reverse ds``

I think the problem is indeed in the `where (x:xs) = reverse ds` part in the `coinChange'` function. Each recursive call reverses the list of denominations. So the `xs` you get there from the pattern match in that `where` clause is the reversed list of denominations without the largest denomination. But that list is still reversed, so you shouldn't pass that as an argument to the `coinChange` or `coinChange'` functions again. You can reverse this list again before passing it to the recursive call, but that is not very efficient. I would suggest only reversing the denominations in the `coinChange` function.

Also, the `coinChange` function can be simplified, because it basically only needs to reverse the denominations and the resulting list.

Here is how that would look:

``coinChange c ds = reverse (coinChange' c (reverse ds))coinChange' c [] = []coinChange' c (x:xs) = (c `quot` x) : coinChange' (c `rem` x) xs``

## The minimum number of coins the sum of which is S

This is a classic Knapsack problem, take a look here for some more information: Wikipedia Knapsack Problem

You should also look at some sorting, specifically sorting from Largest to Smallest values.

## Denominate the amount with the minimum number of coins with a given face value. Greedy problem

One possible approach is backtracking.

Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution. (Wikipedia)

Here, we try to determine the number of coins, for each coin.

The candidates are abandonned, as soon as the total number of coins is higher than the current optimal solution. Moreover, here, in a given situation (at step `i`), we directly calculate the maximum number of coins for `coins[i]`, such that the total sum is not higher than the amount.

Here is a possible implementation:

``#include    <iostream>#include    <vector>#include    <algorithm>std::vector<int> get_change(const std::vector<int>& denominations, int amount) {    std::vector<int> coins = denominations;    std::vector<int> n_coins(coins.size(), 0);    std::vector<int> n_coins_opt(coins.size(), 0);    int n = coins.size();    std::sort(coins.begin(), coins.end(), std::greater<int>());    int sum = 0;    // current sum    int i = 0;      // index of the coin being examined    int n_min_coins = amount / coins[n - 1] + 1;    int n_total_coins = 0;    bool up_down = true;    while (true) {          // UP        if (up_down) {            n_coins[i] = (amount - sum) / coins[i];     // max number of coins[i]            sum += n_coins[i] * coins[i];            n_total_coins += n_coins[i];            if (sum == amount) {                if (n_total_coins < n_min_coins) {                    n_min_coins = n_total_coins;                    n_coins_opt = n_coins;                }                up_down = false;                sum -= n_coins[i] * coins[i];                n_total_coins -= n_coins[i];                n_coins[i] = 0;                i--;            }            else {                if (i == (n - 1) || (n_total_coins >= n_min_coins)) {   // premature abandon                    sum -= n_coins[i] * coins[i];                    n_total_coins -= n_coins[i];                    n_coins[i] = 0;                    up_down = false;                    i--;                }                else {                    i++;                }            }        }        else {            // DOWN            if (i < 0) break;            if (n_coins[i] == 0) {                if (i == 0) break;                i--;            }            else {                sum -= coins[i];                n_coins[i] --;                n_total_coins--;                i++;                up_down = true;            }        }    }    std::vector<int> ans;    for (int i = 0; i < coins.size(); i++)        for (int j = 0; j < n_coins_opt[i]; j++)            ans.push_back(coins[i]);    return ans;}int main() {    std::vector<int> coins = { 1, 6, 9 };    int amount = 30;    auto n_coins = get_change(coins, amount);    for (int i = 0; i < n_coins.size(); i++)            std::cout << n_coins[i] << " ";    std::cout << "\n";    return 1;}``

## python find the minimum number of coins

Looks like a typo: `nickels` vs `nickles`

Edit: now that you've fixed the typo, it looks like it's definitely a rounding issue. Since you're converting from dollars to a whole number of cents, try turning it into an integer before doing any operations.

Change your `n1 = n1 * 100` line to `n1 = int(round(n1 * 100))`. I tried this out on my computer and it seemed to work.

## Finding the minimum set of coins that make a given value

I'm assuming you already know the Dynamic Programming method to find only the minimum number of coins needed. Let's say that you want to find the minimum number of coins to create a total value `K`. Then, your code could be

``vector <int> min_coins(K + 1);min_coins[0] = 0; // base casefor(int k = 1; k <= K; ++k) {    min_coins[k] = INF;    for(int c : coins) { // coins[] contains all values of coins        if(k - c >= 0) {            min_coins[k] = min(min_coins[k], min_coins[k - c] + 1);        }    }}``

Answer to your question: In order to find the actual set of coins that is minimal in size, we can simply keep another array `last_coin[]` where `last_coin[k]` is equal to the coin that was last added to the optimal set of coins for a sum of `k`. To illustrate this:

``vector <int> min_coins(K + 1), last_coin(K + 1);min_coins[0] = 0; // base casefor(int k = 1; k <= K; ++k) {    min_coins[k] = INF;    for(int c : coins) {        if(k - c >= 0) {            if(min_coins[k - c] + 1 < min_coins[k]) {                min_coins[k] = min_coins[k - c] + 1;                last_coin[k] = c; // !!!            }        }    }}``

How does this let you find the set of coins? Let's say we wanted to find the best set of coins that sum to `K`. Then, we know that `last_coin[K]` holds one of the coins in the set, so we can add `last_coin[K]` to the set. After that, we subtract `last_coin[K]` from `K` and repeat until `K = 0`. Clearly, this will construct a (not necessarily the) min-size set of coins that sums to K.

Possible implementation:

``int value_left = K;while(value_left > 0) {    last_coin[value_left] is added to the set    value_left -= last_coin[value_left]}``