## 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 case

for(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 case

for(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]

}

### Related Topics

Postman: How to Check Whether the Field Is Returning Null in the Postman Automation

Pass Dynamic Object in Onclick - Javascript/Jquery

How to Add Node Module to Angular Project If Is Not Schematics Enabled

Changing the Value of Json Object's Key, Changes Other Values Also

How to Clear Input After Onclick With Reactjs

Dynamically Increase and Decrease an Input Text Box Size Depending on Another Selector Width

How to Play Audio File into Channel

How to Convert Gmt Time to Ist Time in JavaScript

How to Convert Raw Mp3 Binary into Blob Url and Play It in Audio Tag

Keep Selected Dropdown Result After Refreshing Page, Jquery

How to Bind on Click Event on Dynamically Created Button in Angular 6

React Jsx - Make Substring in Bold

Detect If a Field Is Updated With JavaScript or Jquery

How to Clear Browsing History Using JavaScript

Accessing Variables from Other Functions Without Using Global Variables

How to Extract Data from Json Nested Objects