Payng with cash - part II
With plenty of pennies, nickels, dimes, quarters and singles ($1 bills) in my pockets I can buy a cup of coffee for $1.50 in any possible way. In how many different ways a cup of coffee can be bought with the exact amount of money ($1.50)?
The answer is 729.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
3 solutions
Brilliant solution. After writing my boring and very long solution, I came up with a shortcut formula similar to yours. It works with any amount of cents. I'll add it to my original solution.
Hello Mr. Hennings. I know that it's to much to ask, but a person reported my solution on "Counting solutions - part II" . If you have time, please check my solution, because you're the expert in solving such problems. Thank you for your consideration.
I
m
i
s
s
e
d
1
a
n
d
g
o
t
7
2
8
.
M
y
a
p
p
r
o
a
c
h
.
D
i
v
i
d
e
t
h
e
p
r
o
b
l
e
m
i
n
t
o
t
w
o
m
a
i
n
g
r
o
u
p
s
a
n
d
s
u
b
g
r
o
u
p
s
.
B
.
.
.
.
.
L
e
t
s
s
t
a
n
d
f
o
r
s
i
n
g
l
e
s
a
n
d
q
s
t
a
n
d
f
o
r
Q
u
a
r
t
e
r
s
.
a
.
s
:
b
.
q
m
e
a
n
i
n
g
′
a
′
s
i
n
g
l
e
s
a
n
d
′
b
′
Q
u
a
r
t
e
r
s
.
a
=
0
o
r
1
,
b
=
0
t
o
6
.
E
v
e
r
y
s
u
b
g
r
o
u
p
o
f
B
w
i
l
l
h
a
v
e
F
I
X
s
a
n
d
q
.
A
.
.
.
.
.
i
n
s
a
m
e
w
a
y
d
f
o
r
d
i
m
e
s
,
n
f
o
r
n
i
c
k
e
l
s
,
p
f
o
r
p
e
n
n
i
e
s
.
x
.
d
⟹
x
d
i
m
e
s
,
y
.
n
:
z
.
p
⟹
y
n
i
c
k
e
l
s
a
n
d
z
p
e
n
n
i
e
s
.
T
h
e
d
i
f
f
e
r
e
n
t
w
a
y
s
t
o
g
e
t
1
5
0
c
e
n
t
s
i
n
a
n
y
s
u
b
g
r
o
u
p
i
s
f
o
u
n
d
i
n
t
h
i
s
,
a
s
p
e
r
t
h
e
t
w
o
g
i
v
e
n
f
o
r
m
u
l
a
s
.
N
T
,
d
=
x
i
s
t
h
e
n
u
m
b
e
r
o
f
w
a
y
s
t
o
g
i
v
e
T
c
e
n
t
s
i
f
d
=
x
i
n
t
h
e
g
i
v
e
n
A
g
r
o
u
p
.
S
u
b
g
r
o
u
p
s
.
B
0
=
0
c
e
n
t
s
,
B
2
5
=
2
5
c
e
n
t
s
,
B
5
0
=
5
0
c
e
n
t
s
,
B
7
5
=
7
5
c
e
n
t
s
,
I
n
t
h
e
n
e
x
t
s
u
b
g
r
o
u
p
s
,
B
K
,
L
⟹
K
c
e
n
t
s
,
i
n
c
l
u
d
e
s
L
s
i
n
g
l
e
,
L
=
0
o
r
1
.
e
.
g
.
B
1
5
0
,
1
=
1
5
0
=
1
.
s
:
2
.
q
.
B
1
0
0
,
0
o
r
B
1
0
0
,
1
=
1
0
0
c
e
n
t
s
,
B
1
2
5
,
0
o
r
B
1
2
5
,
1
=
1
2
5
c
e
n
t
s
,
B
1
5
0
,
0
o
r
B
1
5
0
,
1
=
1
5
0
c
e
n
t
s
.
A
0
=
0
c
e
n
t
s
,
A
2
5
=
2
5
c
e
n
t
s
,
A
5
0
=
5
0
c
e
n
t
s
,
A
7
5
=
7
5
c
e
n
t
s
,
A
1
0
0
=
1
0
0
c
e
n
t
s
,
A
1
2
5
=
1
2
5
c
e
n
t
s
,
A
1
5
0
=
1
5
0
c
e
n
t
s
.
L
e
t
N
u
m
b
e
r
o
f
w
a
y
s
=
M
e
v
e
n
=
(
1
0
c
e
n
t
s
r
e
q
u
i
r
e
d
f
o
r
g
i
v
e
n
A
s
u
b
g
r
o
u
p
,
w
h
e
n
e
v
e
n
+
1
)
2
.
A
n
d
N
u
m
b
e
r
o
f
w
a
y
s
=
M
o
d
d
=
⎝
⎛
1
0
(
c
e
n
t
s
r
e
q
u
i
r
e
d
f
o
r
g
i
v
e
n
A
s
u
b
g
r
o
u
p
w
h
e
n
o
d
d
)
+
5
⎠
⎞
2
+
1
0
c
e
n
t
s
r
e
q
u
i
r
e
d
f
o
r
g
i
v
e
n
A
s
u
b
g
r
o
u
p
+
5
.
W
a
y
s
f
o
r
B
0
+
A
1
5
0
=
(
1
0
1
5
0
+
1
)
2
=
2
5
6
.
W
a
y
s
f
o
r
B
2
5
+
A
1
2
5
=
(
1
0
1
2
5
+
5
)
2
+
1
3
=
1
8
2
.
W
a
y
s
f
o
r
B
5
0
+
A
1
0
0
=
(
1
0
1
0
0
+
1
)
2
=
1
2
1
.
W
a
y
s
f
o
r
B
7
5
+
A
7
5
=
(
1
0
7
5
+
5
)
2
+
8
=
7
2
.
W
a
y
s
f
o
r
B
1
0
0
,
0
+
A
5
0
=
(
1
0
5
0
+
1
)
2
=
3
6
.
W
a
y
s
f
o
r
B
1
0
0
,
1
+
A
5
0
=
(
1
0
5
0
+
1
)
2
=
3
6
.
W
a
y
s
f
o
r
B
1
2
5
,
0
+
A
2
5
=
(
1
0
2
5
+
5
)
2
+
3
=
1
2
.
W
a
y
s
f
o
r
B
1
2
5
,
1
+
A
2
5
=
(
1
0
2
5
+
5
)
2
+
3
=
1
2
.
W
a
y
s
f
o
r
B
1
5
0
,
0
+
A
0
=
(
1
0
0
+
1
)
2
=
1
.
W
a
y
s
f
o
r
B
1
5
0
,
1
+
A
0
=
(
1
0
0
+
1
)
2
=
1
.
2
5
6
+
1
8
2
+
1
2
1
+
7
2
+
3
6
+
3
6
+
1
2
+
1
2
+
1
+
1
=
7
2
9
.
B
e
l
o
w
i
s
d
e
r
i
v
a
t
i
o
n
o
f
t
h
e
t
w
o
f
o
r
m
u
l
a
s
.
W
e
u
s
e
n
o
t
a
t
i
o
n
s
a
s
a
b
o
v
e
.
W
a
y
s
f
o
r
A
1
5
0
.
x
.
d
+
y
.
n
+
z
.
p
=
1
5
0
.
−
−
a
n
e
v
e
n
n
u
m
b
e
r
.
0
.
d
y
=
0
t
o
3
0
(
n
i
c
k
e
l
s
)
.
.
.
.
.
.
.
0
.
n
:
1
5
0
.
p
,
1
.
n
:
1
2
5
.
p
,
2
.
n
:
1
4
0
.
p
,
3
.
n
:
1
3
5
.
p
,
.
d
:
4
.
n
:
1
3
0
.
p
,
.
.
.
2
9
.
n
:
5
.
p
,
:
3
0
.
n
:
0
.
p
.
N
1
5
0
,
d
=
0
=
3
1
1
.
d
y
=
0
t
o
2
8
(
n
i
c
k
e
l
s
)
.
.
.
.
.
.
.
0
.
n
:
1
4
0
.
p
,
1
.
n
:
1
3
5
.
p
,
2
.
n
:
1
3
0
.
p
,
3
.
n
:
1
2
5
.
p
,
.
d
:
4
.
n
:
1
2
0
.
p
,
.
.
.
2
7
.
n
:
5
.
p
,
:
2
8
.
n
:
0
.
p
.
N
1
5
0
,
d
=
1
=
2
9
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1
3
.
d
y
=
0
t
o
4
(
n
i
c
k
e
l
s
)
.
.
.
.
.
.
.
0
.
n
:
2
0
p
,
1
.
n
:
1
5
p
,
2
.
n
:
1
0
p
,
.
.
.
4
.
n
:
0
p
.
N
1
5
0
,
d
=
1
3
=
5
1
4
.
d
y
=
0
t
o
4
(
n
i
c
k
e
l
s
)
.
.
.
.
.
.
.
0
.
n
:
1
0
p
,
1
.
n
:
5
p
,
2
.
n
:
0
p
,
N
1
5
0
,
d
=
1
3
=
3
1
5
.
d
y
=
0
(
n
i
c
k
e
l
s
)
.
.
.
.
.
.
.
.
0
.
n
:
0
.
p
N
1
5
0
,
d
=
1
5
=
1
S
o
w
e
s
e
e
t
h
a
t
t
o
g
e
t
1
5
0
c
e
n
t
s
f
r
o
m
d
,
n
,
p
w
e
h
a
v
e
1
+
3
+
5
+
.
.
.
+
2
7
+
2
9
+
3
1
=
(
2
3
0
+
1
)
2
=
2
5
6
w
a
y
s
.
N
o
t
e
:
−
3
0
i
s
t
h
e
n
u
m
b
e
r
o
f
n
i
c
k
e
l
s
w
e
c
a
n
h
a
v
e
i
f
o
n
l
y
n
i
c
k
e
l
s
w
e
r
e
u
s
e
d
t
o
o
b
t
a
i
n
1
5
0
c
e
n
t
s
.
O
r
i
t
i
s
(
5
c
e
n
t
s
r
e
q
u
i
r
e
d
)
.
⟹
w
h
e
n
c
e
n
t
s
r
e
q
u
i
r
e
d
a
r
e
E
V
E
N
t
h
e
n
u
m
b
e
r
w
a
y
s
=
(
1
0
c
e
n
t
s
r
e
q
u
i
r
e
d
+
1
)
2
~~\\
~~\\
Applying~the~same~method.......\\
~~\\
{\color{#3D99F6}{Ways~for~A_{125}}.~~~~~~x.d+y.n+z.p=125-an~odd~number.\\ ~~~~\\
0
.
d
y
=
0
t
o
2
5
(
n
i
c
k
e
l
s
)
.
.
.
.
.
.
.
0
.
n
:
1
2
5
.
p
,
1
.
n
:
1
2
0
.
p
,
2
.
n
:
1
1
5
.
p
,
3
.
n
:
1
1
0
.
p
,
4
.
n
:
1
0
5
.
p
,
.
.
.
2
4
.
n
:
5
.
p
,
2
5
.
n
:
0
.
p
.
N
1
2
5
,
d
=
0
=
2
6
1
.
d
y
=
0
t
o
2
3
(
n
i
c
k
e
l
s
)
.
.
.
.
.
.
.
0
.
n
:
1
1
5
.
p
,
1
.
n
:
1
1
0
.
p
,
2
.
n
:
1
0
5
.
p
,
3
.
n
:
1
0
0
.
p
,
4
.
n
:
9
5
.
p
,
.
.
.
2
2
.
n
:
5
.
p
,
2
3
.
n
:
0
.
p
.
N
1
5
0
,
d
=
1
=
2
4
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1
0
.
d
y
=
0
t
o
5
(
n
i
c
k
e
l
s
)
.
.
.
.
.
.
.
0
.
n
:
2
5
p
,
1
.
n
:
2
0
p
,
2
.
n
:
1
5
p
,
.
.
.
4
.
n
:
5
p
5
n
:
0
.
p
N
1
2
5
,
d
=
1
0
=
6
1
1
.
d
y
=
0
t
o
3
(
n
i
c
k
e
l
s
)
.
.
.
.
.
.
.
0
.
n
:
1
5
p
,
1
.
n
:
1
0
p
,
2
.
n
:
5
,
N
1
2
5
,
d
=
1
1
=
4
1
2
.
d
y
=
0
(
n
i
c
k
e
l
s
)
.
.
.
.
.
.
.
.
0
.
n
:
5
.
p
1
.
n
:
0
p
N
1
2
5
,
d
=
1
2
=
2
S
o
w
e
s
e
e
t
h
a
t
t
o
g
e
t
1
2
5
c
e
n
t
s
f
r
o
m
d
,
n
,
p
w
e
h
a
v
e
2
+
4
+
6
+
8
+
1
0
+
1
2
+
1
4
+
.
.
.
+
2
2
+
2
4
+
2
6
=
2
∗
(
1
+
2
+
3
+
4
+
5
+
6
+
7
+
.
.
.
+
1
1
+
1
2
+
1
3
)
=
2
∗
2
1
3
∗
1
4
=
1
3
2
+
1
3
=
(
2
2
5
+
1
)
2
+
(
2
2
5
+
1
)
.
⟹
W
h
e
n
t
h
e
c
e
n
t
s
r
e
q
u
i
r
e
d
i
s
O
D
D
,
n
u
m
b
e
r
o
f
w
a
y
s
w
e
c
a
n
u
s
e
d
,
n
a
n
d
p
.
=
(
1
0
c
e
n
t
s
r
e
q
u
i
r
e
d
+
5
)
2
+
(
1
0
c
e
n
t
s
r
e
q
u
i
r
e
d
+
5
)
.
This algorithm can be done in any programming language that supports recursion. It helps if the language also supports memorization of previously computed results.
I can choose to use 0 ≤ s ≤ 1 singles. If I use s singles, I need to make up the balance of 1 5 0 − 1 0 0 s cents out of quarters, dimes, nickels and pennies, and so I can use q quarters, where 0 ≤ q ≤ 6 − 4 s . I then have to make the up the balance of 1 5 0 − 1 0 0 s − 2 5 q cents out of dimes, nickels and pennies, and so I can use d dimes, where 0 ≤ d ≤ ⌊ 1 5 − 1 0 s − 2 5 q ⌋ . I can then choose to use n nickels, where 0 ≤ n ≤ 3 0 − 2 0 s − 5 q − 2 d , and then make up the difference in pennies. Thus the number of methods of paying is N = s = 0 ∑ 1 q = 0 ∑ 6 − 4 s d = 0 ∑ ⌊ 1 5 − 1 0 s − 2 5 q ⌋ ( 3 1 − 2 0 s − 5 q − 2 d ) = 7 2 9