Consider a set of coin denominations as: {1$, 2$, 5$, 10$}. Determine the number of ways to make 11$ using different combinations of these coins like the result table. For example, the highlighted row means using eleven 1$ coins to make a total of 11$.
📌 Challenge Details and Links
Challenge Number: 70
Challenge Difficulty: ⭐⭐⭐⭐⭐
📥Download Sample File
📥Link to the solutions on LinkedIn
Solving the challenge of Coin Change Problem! with Power Query
Power Query solution 1 for Coin Change Problem!, proposed by Omid Motamedisedeh:
let
JavaScript = Web.Page(
"<script> var output = '{'; var first = true; for (var i = 0; i <= 11; i++) { for (var j = 0; j <= 5; j++) { for (var k = 0; k <= 2; k++) { for (var z = 0; z <= 1; z++) { if (i + 2 * j + 5 * k + 10 * z === 11) { if (!first) { output += ', '; } output += '{' + i + ',' + j + ',' + k + ',' + z + '}'; first = false; } } } } } output += '}'; document.write(output); </script>"
),
Result = Table.FromRows(
Expression.Evaluate(JavaScript{0}[Data]{0}[Children]{1}[Children]{0}[Text]),
{"1$", "2$", "5$", "10$"}
)
in
ResultPower Query solution 2 for Coin Change Problem!, proposed by Omid Motamedisedeh:
Table.FromRows(
List.Select(
List.Generate(
() => 0,
each Q(_, P(12, 3)) < 12,
each _ + 1,
each {M(Q(_, P(12, 3)), 12), M(Q(_, P(12, 2)), 12), M(Q(_, 12), 12), M(_, 12)}
),
each (_{0} + _{1} * 2 + _{2} * 5 + _{3} * 10) = 11
),
{"1$", "2$", "5$", "10$"}
)Power Query solution 3 for Coin Change Problem!, proposed by Zoran Milokanović:
let
Source = 11,
H = {1, 2, 5, 10},
S = Table.FromRows(
List.Select(
List.Accumulate(
H,
{{}},
(b, n) => List.TransformMany(b, each {0 .. Number.RoundDown(Source / n)}, (i, _) => i & {_})
),
each List.Sum(List.Transform(List.Positions(H), (m) => H{m} * _{m})) = Source
),
List.Transform(H, each Text.From(_) & "$")
)
in
SPower Query solution 4 for Coin Change Problem!, proposed by Aditya Kumar Darak 🇮🇳:
let
Total = 11,
Coins = {1, 2, 5, 10},
Generate = List.Generate(
() => [a = - 1, d = {{}}],
each [a] < List.Count(Coins),
each [
a = [a] + 1,
b = Coins{a},
c = Number.RoundDown(Total / b),
d = List.TransformMany(
[d],
(x) => {0 .. c},
(x, y) =>
x
& {
[
n = y,
t = n * b,
rt = if [a] < 0 then t else x{[a]}[rt] + t,
c = if [a] < 0 then {n} else x{[a]}[c] & {n}
]
}
)
],
each [d]
),
Transform = List.Transform(
List.Last(Generate),
each [L = List.Last(_), R = if L[rt] = Total then L[c] else null][R]
),
Return = Table.FromRows(
List.RemoveNulls(Transform),
List.Transform(Coins, each "$" & Text.From(_))
)
in
ReturnPower Query solution 5 for Coin Change Problem!, proposed by Aditya Kumar Darak 🇮🇳:
let
Total = 11,
Coins = {1, 2, 5, 10},
Generate = List.Generate(
() => [a = - 1, d = {{}}],
each [a] < List.Count(Coins),
each [
a = [a] + 1,
b = Coins{a},
c = Number.RoundDown(Total / b),
d = List.TransformMany([d], (x) => {0 .. c}, (x, y) => x & {[n = y, t = n * b]})
],
each [d]
),
Transform = List.Transform(
List.Last(Generate),
each [
T = List.Sum(List.Transform(_, (f) => f[t])),
N = List.Transform(_, (f) => f[n]),
R = if T = Total then N else null
][R]
),
Return = Table.FromRows(
List.RemoveNulls(Transform),
List.Transform(Coins, each "$" & Text.From(_))
)
in
ReturnPower Query solution 6 for Coin Change Problem!, proposed by Alejandro Simón 🇵🇦 🇪🇸:
let
A = {1, 2, 5, 10},
Tbl = Table.FromRows(
{List.Transform(A, each List.Transform({0 .. Number.RoundDown(11 / _)}, (x) => x * _))},
List.Transform(A, Text.From)
),
Tbl2 = List.Accumulate(List.Transform(A, Text.From), Tbl, (s, c) => Table.ExpandListColumn(s, c)),
Sel = Table.Sort(Table.SelectRows(Tbl2, each List.Sum(Record.ToList(_)) = 11), {{"1", 1}}),
Sol = List.Accumulate(
List.Transform(A, Text.From),
Sel,
(s, c) => Table.TransformColumns(s, {{c, each _ / Number.From(c)}})
)
in
SolPower Query solution 7 for Coin Change Problem!, proposed by Alexis Olson:
let
Total = 11,
Coins = {1, 2, 5, 10},
Candidates = List.Transform(Coins, (c) => {0 .. Number.IntegerDivide(Total, c)}),
CrossProduct = (L as list) as list =>
List.Accumulate(
L,
{},
(prod, curr) =>
if prod = {} then
List.Transform(curr, each {_})
else
List.Combine(List.Transform(prod, (a) => List.Transform(curr, (b) => a & {b})))
),
TotalValue = (coins as list, counts as list) as number =>
List.Sum(List.Transform(List.Zip({coins, counts}), List.Product)),
ValidCandidates = List.Select(CrossProduct(Candidates), each TotalValue(Coins, _) = Total),
Results = Table.FromRows(ValidCandidates, List.Transform(Coins, each Number.ToText(_) & "$"))
in
ResultsPower Query solution 8 for Coin Change Problem!, proposed by 🇮🇷 Navid Esmaeilzadeh اسماعیل زاده:
let
F = Table.FromColumns(
{
{{0 .. Number.RoundDown(11 / 1, 0)}},
{{0 .. Number.RoundDown(11 / 2, 0)}},
{{0 .. Number.RoundDown(11 / 5, 0)}},
{{0 .. Number.RoundDown(11 / 10, 0)}}
},
{"1$", "2$", "5$", "10$"}
),
#"1$" = Table.ExpandListColumn(F, "1$"),
#"2$" = Table.ExpandListColumn(#"1$", "2$"),
#"5$" = Table.ExpandListColumn(#"2$", "5$"),
#"10$" = Table.ExpandListColumn(#"5$", "10$"),
G = Table.TransformColumns(
#"10$",
{
{"1$", each _ * 1, Int64.Type},
{"2$", each _ * 2, Int64.Type},
{"5$", each _ * 5, Int64.Type},
{"10$", each _ * 10, Int64.Type}
}
),
H = Table.AddColumn(G, "Sum", each [#"1$"] + [#"2$"] + [#"5$"] + [#"10$"]),
I = Table.SelectRows(H, each [Sum] = 11),
J = Table.RemoveColumns(I, {"Sum"}),
K = Table.TransformColumns(
J,
{{"1$", each _ / 1}, {"2$", each _ / 2}, {"5$", each _ / 5}, {"10$", each _ / 10}}
),
Sol = Table.Sort(
K,
{
{"1$", Order.Descending},
{"2$", Order.Descending},
{"5$", Order.Descending},
{"10$", Order.Descending}
}
)
in
SolSolving the challenge of Coin Change Problem! with Excel
Excel solution 1 for Coin Change Problem!, proposed by Bo Rydobon 🇹🇭:
=LET(
t,
300,
c,
{10,
5,
2,
1}, b,
LAMBDA(
b,
a,
i,
LET(
n,
ROWS(
a
),
IF(
n>1,
VSTACK(
b(
b,
TAKE(
a,
n/2
),
i
),
b(
b,
DROP(
a,
n/2
),
i
)
),
LET(
r,
--TEXTBEFORE(
a,
" "
),
f,
TEXTAFTER(
a,
" "
),
s,
SEQUENCE(
,
@r/i+1,
0,
i
),
TOCOL(
IFS(
IF(
i=MIN(
c
),
r=s,
r>=s
),
r-s&" "&f&TEXT(
s,
"000"
)
),
3
)
)
)
)
), VSTACK(
c,
MID(
REDUCE(
t&" ",
c,
LAMBDA(
a,
i,
b(
b,
a,
i
)
)
),
SEQUENCE(
,
4,
3,
3
),
3
)/c
)
)Excel solution 2 for Coin Change Problem!, proposed by Bo Rydobon 🇹🇭:
=PRODUCT(
INT(
100/{1,
2,
5,
10}
)+1
) =1,
189,
881 for all possible combination more than 2^20 cause error
This one work is worth more than 99$
for 200$ takes 1.5 seconds to create 15,
211 combinations
=LET(
t,
200,
c,
{1,
2,
5,
10}, MID(
TEXTAFTER(
REDUCE(
t&" ",
c,
LAMBDA(
a,
n,
LET(
r,
--TEXTBEFORE(
a,
" "
),
s,
SEQUENCE(
,
@r/n+1,
0,
n
),
TOCOL(
IFS(
IF(
n=MAX(
c
),
r=s,
r>=s
),
r-s&" "&TEXTAFTER(
a,
" "
)&TEXT(
s,
"000"
)
),
3
)
)
)
),
" "
),
SEQUENCE(
,
COUNT(
c
),
,
3
),
3
)/c
)Excel solution 3 for Coin Change Problem!, proposed by Bo Rydobon 🇹🇭:
=LET(
t,
11,
c,
--SUBSTITUTE(
H2:K2,
"$", ),
p,
--MID(
REDUCE(
"",
INT(
t/c
)+1,
LAMBDA(
a,
n,
TOCOL(
a&TEXT(
SEQUENCE(
,
n,
0
),
"00"
)
)
)
),
SEQUENCE(
,
COUNT(
c
),
,
2
),
2
),
FILTER(
p,
MMULT(
p,
TOCOL(
c
)
)=t
)
)Excel solution 4 for Coin Change Problem!, proposed by محمد حلمي:
= 20736 = 12*12*12*12 =PERMUTATIONA(
12,
4
)
=LET(
n,
11,
c,
{1,
2,
5,
10}, i,
MID(
BASE(
SEQUENCE(
12^4,
,
12^4,
-1
),
12,
4
),
SEQUENCE(
,
4
),
1
), m,
IFERROR(
--i,
CODE(
i
)-55
)*c,
v,
BYROW(
m,
LAMBDA(
a,
SUM(
a
)
)
), VSTACK(
c,
FILTER(
m,
v=n
)/c
)
)Excel solution 5 for Coin Change Problem!, proposed by Julian Poeltl:
=LET(
S,
SEQUENCE(
12,
,
0
),
M,
L_MixLargeArraysColumnsbyColumntogehter_AllPossibilities_INT(
HSTACK(
S,
S,
S,
S
)
),
P,
M*HSTACK(
1,
2,
5,
10
),
SORT(
FILTER(
M,
BYROW(
P,
LAMBDA(
A,
SUM(
A
)
)
)=11
)*1,
1,
-1
)
)
L_MixLargeArraysColumnsbyColumntogehter_AllPossibilities_INT:
=LAMBDA(
Array1,
[Array2],
LET(
z,
IF(
ISOMITTED(
Array2
),
Array1,
HSTACK(
Array1,
Array2
)
),
D,
"|",
c,
SEQUENCE(
,
COLUMNS(
z
)
),
re,
REDUCE(
"",
c,
LAMBDA(
A,
n,
UNIQUE(
TOCOL(
A&D&TOROW(
INDEX(
z,
,
n
),
3
)
)
)
)
),
TEXTBEFORE(
TEXTAFTER(
re,
D,
c
),
D,
,
,
1
)
)
)Excel solution 6 for Coin Change Problem!, proposed by Kris Jaganah:
=LET(a,
11,
b,
{1,
2,
5,
10},
c,
DROP(
REDUCE(
"",
b,
LAMBDA(
x,
y,
VSTACK(
x,
SEQUENCE(
a/y,
,
y,
0
)
)
)
),
1
),
d,
UNIQUE(
DROP(
REDUCE(
"",
c,
LAMBDA(
v,
w,
VSTACK(
v,
v&","&w
)
)
),
1
)
),
e,
MAP(
d,
LAMBDA(
u,
SUM(
--REGEXEXTRACT(
u,
"[0-9]+",
1
)
)=a
)
),
f,
--(TEXTSPLIT(
CONCAT(
TEXTAFTER(
FILTER(
d,
e
),
","
)&"#"
),
",",
"#",
1,
,
0
)),
VSTACK(b,
--TRANSPOSE(TEXTSPLIT(TEXTJOIN("#",
1,
MAP(b,
LAMBDA(s,
ARRAYTOTEXT(BYROW(f,
LAMBDA(t,
SUM(--(s=t)))))))),
",",
"#"))))Excel solution 7 for Coin Change Problem!, proposed by Bilal Mahmoud kh.:
=LET(
a,
TEXTSPLIT(
TEXTJOIN(
"|",
,
MAP(
SEQUENCE(
12,
,
11,
-1
),
LAMBDA(
x,
TEXTJOIN(
"|",
,
MAP(
SEQUENCE(
6,
,
5,
-1
),
LAMBDA(
y,
TEXTJOIN(
"|",
,
MAP(
SEQUENCE(
3,
,
2,
-1
),
LAMBDA(
z,
TEXTJOIN(
"|",
,
MAP(
SEQUENCE(
2,
,
1,
-1
),
LAMBDA(
n,
x&"-"&y&"-"&z&"-"&n
)
)
)
)
)
)
)
)
)
)
)
),
"-",
"|"
),
b,
FILTER(
a,
BYROW(
a,
LAMBDA(
d,
SUMPRODUCT(
--d,
H2:E2
)=11
)
)
),
b
)Excel solution 8 for Coin Change Problem!, proposed by LEONARD OCHEA 🇷🇴:
=LET(
h,
{10,
5,
2,
1},
c,
HEX2DEC(
MID(
BASE(
SEQUENCE(
12^4,
,
0
),
12,
4
),
SEQUENCE(
,
4
),
1
)
),
VSTACK(
h,
FILTER(
c,
MMULT(
c,
TOCOL(
h
)
)=11
)
)
)Excel solution 9 for Coin Change Problem!, proposed by Mark Biegert:
=LET(tbl,
MAKEARRAY(12^4,
4,
LAMBDA(r,
c,
MOD(QUOTIENT(r,
12^(c-1)),
12))),
VSTACK(
{"1$",
"2$",
"5$",
"10$"},
UNIQUE(
FILTER(
tbl,
MMULT(
tbl,
{1;2;5;10}
)=11
)
)
)
)Excel solution 10 for Coin Change Problem!, proposed by Peter Bartholomew:
=LAMBDA(
amt,
denom, LET( maxCount,
QUOTIENT(
amt,
denom
), count,
SEQUENCE(
1 + maxCount,
,
0
), amount,
amt - count * denom, HSTACK(
count,
amount
) ))Excel solution 11 for Coin Change Problem!, proposed by Pieter de B.:
=LET(
n,
{1,
2,
5,
10},
x,
LAMBDA(
a,
b,
LET(
c,
INT(
11/b
),
TOCOL(
TOROW(
a
)+SEQUENCE(
1+c,
,
0,
b
)
)
)
),
z,
x(
x(
x(
x(
0,
1
),
2
),
5
),
10
),
y,
LAMBDA(
a,
b,
LET(
c,
INT(
11/b
),
TOCOL(
TOROW(
a
)&"|"&SEQUENCE(
1+c,
,
0,
b
)
)
)
),
VSTACK(
n&"$",
TEXTSPLIT(
TEXTAFTER(
TOCOL(
IFS(
z=11,
y(
y(
y(
y(
0,
1
),
2
),
5
),
10
)
),
2
),
"|",
{1,
2,
3,
4}
),
"|"
)/n
)
)Solving the challenge of Coin Change Problem! with Python
Python solution 1 for Coin Change Problem!, proposed by Konrad Gryczan, PhD:
import pandas as pd
path = "CH-070 coin change problem.xlsx"
test = pd.read_excel(path, usecols = "H:K", skiprows=1, nrows = 12).sort_values(['1$', '2$', '5$', '10$']).reset_index(drop=True)
target = 11
coins = [1, 2, 5, 10]
counts = pd.DataFrame(
index=pd.MultiIndex.from_product([range(target + 1)] * 4, names=['n1', 'n2', 'n3', 'n4'])
).reset_index()
combinations = counts.assign(
total=lambda x: x['n1'] * coins[0] + x['n2'] * coins[1] + x['n3'] * coins[2] + x['n4'] * coins[3]
).query('total == @target').drop('total', axis=1).sort_values(['n1', 'n2', 'n3', 'n4']).reset_index(drop=True)
combinations.columns = test.columns
print(combinations.equals(test)) # True
Solving the challenge of Coin Change Problem! with R
R solution 1 for Coin Change Problem!, proposed by Konrad Gryczan, PhD:
library(tidyverse)
library(readxl)
path = "files/CH-070 coin change problem.xlsx"
test = read_excel(path, range = "H2:K14") %>% arrange(`1$`,`2$`,`5$`,`10$`)
target <- 11
coins <- c(1, 2, 5, 10)
counts <- expand.grid(
n1 = 0:(target / coins[1]),
n2 = 0:(target / coins[2]),
n3 = 0:(target / coins[3]),
n4 = 0:(target / coins[4])
)
combinations <- counts %>%
mutate(
total = n1 * coins[1] + n2 * coins[2] + n3 * coins[3] + n4 * coins[4]
) %>%
filter(total == target) %>%
select(-total) %>%
arrange(n1,n2,n3,n4)
all.equal(combinations, test, check.attributes = FALSE)
# [1] TRUE