Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Numbers At Most N Given Digit Set
Bookmark
Counting
DP over Suffixes
Input
{3,4,5}, n=345
{1,3,5,7}, n=100
{1,4,9}, n=1000
{7}, n=8
Custom
digits
=
[3, 4, 5]
,
n
=
345
n =
345
digits = {
3,4,5
} · d=3
3
S[0]
4
S[1]
5
S[2]
n
count L-digit numbers ≤ n, then add every shorter number
count = 0
build numbers digit by digit, keeping them ≤ n
n =
345
digits = {
3,4,5
} · d=3
3
S[0]
4
S[1]
5
S[2]
n
count L-digit numbers ≤ n, then add every shorter number
count = 0
build numbers digit by digit, keeping them ≤ n
n =
345
digits = {
3,4,5
} · d=3
3
S[0]
4
S[1]
5
S[2]
n
every 1-digit number from the set is below n: count += d^1
count = 3
n =
345
digits = {
3,4,5
} · d=3
3
S[0]
4
S[1]
5
S[2]
n
compare each allowed digit to S[0] = 3
3
=
4
>
5
>
count = 12
n =
345
digits = {
3,4,5
} · d=3
3
S[0]
4
S[1]
5
S[2]
n
compare each allowed digit to S[0] = 3
3
=
4
>
5
>
count = 12
'5' > 3
→ would exceed n → skip
n =
345
digits = {
3,4,5
} · d=3
3
S[0]
4
S[1]
5
S[2]
n
compare each allowed digit to S[1] = 4
3
<
4
=
5
>
count = 12
n =
345
digits = {
3,4,5
} · d=3
3
S[0]
4
S[1]
5
S[2]
n
compare each allowed digit to S[1] = 4
3
<
4
=
5
>
count = 15
'4' = 4
→ stay tight → dp[1] += dp[2] =
0
n =
345
digits = {
3,4,5
} · d=3
3
S[0]
4
S[1]
5
S[2]
n
compare each allowed digit to S[1] = 4
3
<
4
=
5
>
count = 15
n =
345
digits = {
3,4,5
} · d=3
3
S[0]
4
S[1]
5
S[2]
n
compare each allowed digit to S[2] = 5
3
<
4
<
5
=
count = 17
'4' < 5
→ suffix free → dp[2] += d^0 =
1
n =
345
digits = {
3,4,5
} · d=3
3
S[0]
4
S[1]
5
S[2]
n
compare each allowed digit to S[2] = 5
3
<
4
<
5
=
count = 17
n =
345
digits = {
3,4,5
} · d=3
3
S[0]
4
S[1]
5
S[2]
n
count L-digit numbers ≤ n, then add every shorter number
count = 18
count = 18
algo
master
.
io
Step:
Count positive integers ≤ 345 whose digits all come from {3, 4, 5} (repeats allowed).
0 / 20
Input
{3,4,5}, n=345
{1,3,5,7}, n=100
{1,4,9}, n=1000
{7}, n=8
Custom
digits
=
[3, 4, 5]
,
n
=
345
0 / 20
algo
master
.
io
Step:
Count positive integers ≤ 345 whose digits all come from {3, 4, 5} (repeats allowed).
