15,306,142 members
See more:
So I have scoured the internet for this but I haven't found a solution, yet.

The Problem: We have a number of supermarkets in the UK and each of them has its own set of voucher denominations. E.g. Tesco is [100, 75, 50, 25, 10], and ASDA is [100, 50, 25, 20, 10, 5].

I need a function that takes the total amount and returns an array of various denominations that make up that amount. For example:

JavaScript
```let amount = 80;
getDenominations(amount);
// this should return 50 x 1, 10 x 3 for Tesco
// and 50 x 1, 25 x 1, 5 x 1 for Asda```

There are plenty of algorithms out there for calculating change with 'greedy' approach, but none of them work primarily because the last denomination for each supermarketing is anything but 1. Greedy approach works fine only when the last denomination is one, so it can easily assign 1s to the remainder.

What I have tried:

I have tried a number of methods that seem to work most of the time, but on occasions, they fail.

Of course, I understand there will be some numbers e.g. 23 that will always have a remainder, and I am fine with that. I am only after numbers that logically can be divided up without leaving a remainder.

For example, with the work I've done so far, I can quite successfully process 10, 20, 30, 35, 40, 45, 50... with Tesco vouchers. But with 55 it fails, and the reason for that is:

It comes across 25, times that by 2, to get 50, and then fails to find a denomination for the remaining 5. The other way around, it finds 10, times that by 5 to get 50, but is left with a 5 and no denomination for it. Ideally, it should simply get one of 25 and 3 of 10 to get 55.

Any ideas how to solve this problem?

Here is one variation of my numerous attempts:

JavaScript
```function calculateVouchersDenominations(amount, voucher) {

var vouchers = {
'asda': [100, 50, 25, 20, 10, 5],
'tesco': [100, 75, 50, 25, 10],
'sainsburys': [100, 50, 25, 10],
'morrisons': [45, 30, 25, 15, 10, 5],
'one4all': [45, 30, 25, 15, 10, 5],
'primark': [200, 190, 180, 170, 160, 150, 140, 130, 120, 110, 100, 90, 80, 70, 60, 50, 40, 30, 20, 10, 5],
'iceland': [200, 100, 50, 10]
}

var denominations = vouchers[voucher];

if (denominations === undefined)
return [];

var voucherCounter = [];
denominations.forEach(function (row, i) {
voucherCounter[i] = 0;
});

// count denominations using
// Greedy approach
for (i = 0; i < denominations.length; i++)
{
if (amount >= denominations[i])
{
voucherCounter[i] = parseInt(amount / denominations[i]);
amount = amount - voucherCounter[i] * denominations[i];
}
}

var out = [];
for (i = 0; i < denominations.length; i++)
{
if (voucherCounter[i] !== 0)
{
out[denominations[i]] = voucherCounter[i];
}
}

return out;
}```
Posted
Updated 2-Aug-21 14:37pm
v2
Patrice T 2-Aug-21 14:36pm

Show your code so we see why you failed.
Saleem Beg 2-Aug-21 15:09pm

Here is one variation of my numerous attempts:

function calculateVouchersDenominations(amount, voucher) {

var vouchers = {
'asda': [100, 50, 25, 20, 10, 5],
'tesco': [100, 75, 50, 25, 10],
'sainsburys': [100, 50, 25, 10],
'morrisons': [45, 30, 25, 15, 10, 5],
'one4all': [45, 30, 25, 15, 10, 5],
'primark': [200, 190, 180, 170, 160, 150, 140, 130, 120, 110, 100, 90, 80, 70, 60, 50, 40, 30, 20, 10, 5],
'iceland': [200, 100, 50, 10]
}

var denominations = vouchers[voucher];

if (denominations === undefined)
return [];

var voucherCounter = [];
denominations.forEach(function (row, i) {
voucherCounter[i] = 0;
});

// count denominations using
// Greedy approach
for (i = 0; i < denominations.length; i++)
{
if (amount >= denominations[i])
{
voucherCounter[i] = parseInt(amount / denominations[i]);
amount = amount - voucherCounter[i] * denominations[i];
}
}

var out = [];
for (i = 0; i < denominations.length; i++)
{
if (voucherCounter[i] !== 0)
{
out[denominations[i]] = voucherCounter[i];
}
}

return out;
}
Patrice T 2-Aug-21 15:20pm

Saleem Beg 2-Aug-21 15:24pm

Thanks!
Patrice T 2-Aug-21 16:07pm

"I need a function that takes the total amount and returns an array of various denominations that make up that amount."
Are you looking for 1 solution per supermarket or all possible solutions per supermarket ?
Saleem Beg 2-Aug-21 17:33pm

Ideally, it should be one function that intelligently works out the sum for different combinations, so potentially one can throw any supermarket (or anything else for that matter) and it should work.

Another variation I tried was to create a powerset of all the vouchers. So it creates combinations of all the different denominations and processes them through the above function. It is probably the most accurate solution I have found so far, but even then in some cases, it fails. E.g. with number 55 it should look at the subset [25,10] and return 25 x 1 and 10 x 3. But it deals with 25 first (rightly so) but times it by 2 to get 50, and then cannot find any denomination for the remaining 5. If I were to reverse the subset (10, 25), it would times 10 by 5 to get 50, but again, be left with 5.

## Solution 2

Quote:
I have tried a number of methods that seem to work most of the time, but on occasions, they fail.

Never heard of backtracking algorithm and recursion algorithm ?
Backtracking - Wikipedia[^]
Recursion (computer science) - Wikipedia[^]