Numbers At Most N Given Digit Set
Given an array of digits which is sorted in non-decreasing order. You can write numbers using each digits[i] as many times as you want. For example, if digits = ['1','3','5'], you may write numbers such as '13', '551', and '1351315'.
Return the number of positive integers that can be generated that are less than or equal to a given integer n.
Example 1
Input
digits = ["1","3","5","7"], n = 100Output
20The writable positive integers at most 100 are the 4 one-digit numbers and the 16 two-digit numbers formed from the given digits, for 20 total.
Example 2
Input
digits = ["1","4","9"], n = 1000000000Output
29523There are 3^k writable k-digit numbers for k = 1 through 9, totaling 29523 integers.
Constraints
- 1 <= digits.length <= 9
- digits[i].length == 1
- digits[i] is a digit from '1' to '9'.
- All the values in digits are unique.
- digits is sorted in non-decreasing order.
- 1 <= n <= 10^9