#902
Numbers At Most N Given Digit Set
candidate master · 1575 · lc hard +32 · verified · 44.6% accepted · 1,466 likes · top 27%
Description
You are given a sorted array of digit characters digits, each of which may be reused any number of times when building positive integers. Given an integer n, return how many positive integers at most n can be constructed using only the digits in digits.
Example 1:
Input: digits = ["1","3","5","7"], n = 100
Output: 20
Explanation:
The 20 numbers that can be written are:
1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.
Example 2:
Input: digits = ["1","4","9"], n = 1000000000
Output: 29523
Explanation:
We can write 3 one digit numbers, 9 two digit numbers, 27 three digit numbers,
81 four digit numbers, 243 five digit numbers, 729 six digit numbers,
2187 seven digit numbers, 6561 eight digit numbers, and 19683 nine digit numbers.
In total, this is 29523 integers that can be written using the digits array.
Example 3:
Input: digits = ["7"], n = 8
Output: 1
Code
1
2
3