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
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
0
dp[0]
0
dp[1]
0
dp[2]
0
base
dp
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
0
dp[0]
0
dp[1]
0
dp[2]
0
base
dp
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
shorter-length numbers are free; dp counts the same-length ones ≤ n
0
dp[0]
0
dp[1]
0
dp[2]
0
base
dp
pow = [
1, 3, 9, 27
] (d^0 … d^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[2] = 5
3
<
4
<
5
=
dp[0]
dp[1]
1
dp[2]
1
base
dp
'3' < 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
=
dp[0]
dp[1]
2
dp[2]
1
base
dp
'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[1] = 4
3
<
4
=
5
>
dp[0]
3
dp[1]
3
dp[2]
1
base
dp
'3' < 4
→ suffix free → dp[1] += d^1 =
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[1] = 4
3
<
4
=
5
>
dp[0]
6
dp[1]
3
dp[2]
1
base
dp
'4' = 4
→ stay tight → dp[1] += dp[2] =
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
>
6
dp[0]
6
dp[1]
3
dp[2]
1
base
dp
'3' = 3
→ stay tight → dp[0] += dp[1] =
6
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
>
6
dp[0]
6
dp[1]
3
dp[2]
1
base
dp
'4' > 3
→ would exceed n → skip
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
6
dp[0]
6
dp[1]
3
dp[2]
1
base
dp
same length
6
+ shorter
12
=
18
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
6
dp[0]
6
dp[1]
3
dp[2]
1
base
dp
count = 18
algo
master
.
io
Step:
Count positive integers ≤ 345 whose digits all come from {3, 4, 5} (repeats allowed).
0 / 13
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 / 13
algo
master
.
io
Step:
Count positive integers ≤ 345 whose digits all come from {3, 4, 5} (repeats allowed).
