Given an array of digits which is sorted in non-decreasing order. You can write numbers using each digits[i] as many times as we want. For example, if digits = ['1','3','5'], we 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 = 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
Constraints:
1 <= digits.length <= 9digits[i].length == 1digits[i] is a digit from '1' to '9'.digits are unique.digits is sorted in non-decreasing order.1 <= n <= 109Problem Overview: You are given a set of allowed digits and an integer N. Count how many positive integers less than or equal to N can be formed using only those digits, where digits can be reused any number of times.
Approach 1: Backtracking Enumeration (Exponential)
This method generates all valid numbers using recursive backtracking. Start with an empty number and repeatedly append each digit from the allowed set. Stop when the constructed number exceeds N. Every valid number encountered is counted. The approach directly explores the search space of possible numbers and uses simple recursion with pruning when values exceed N. Time complexity is roughly O(k^d) where k is the number of digits and d is the number of digits in N. Space complexity is O(d) due to recursion depth. This approach is easy to implement but becomes slow when N has many digits.
Approach 2: Digit Dynamic Programming (Optimal)
The optimal solution uses digit DP and combinatorics to count valid numbers without enumerating them. First count all numbers with fewer digits than N. If the digit set size is k and the length of N is d, then there are k^1 + k^2 + ... + k^(d-1) valid numbers of smaller length. Next process the digits of N from left to right. For each position, count how many digits from the allowed set are smaller than the current digit of N. Each such choice contributes k^(remaining positions) possibilities. If the current digit of N is not in the digit set, the process stops early because larger prefixes would exceed N. If all digits match valid choices, include N itself. This approach uses ideas from dynamic programming, math, and array processing. Time complexity is O(d * k) and space complexity is O(1).
Recommended for interviews: Interviewers expect the digit DP counting approach. Brute-force backtracking shows you understand the search space, but it does not scale. The DP/combinatorics method demonstrates strong reasoning about digit positions, prefix constraints, and counting techniques—skills frequently tested in hard problems involving dynamic programming and numeric strings.
This approach uses backtracking to consider all possible numbers that can be formed using the given digits. It constructs numbers digit by digit and checks if they are valid (less than or equal to n). If a number reaches the length of n, it checks if it should continue further based on the current digit comparison.
In this solution, the function converts `n` to a string and checks each digit position recursively. It first adds up all possible numbers with fewer digits. While iterating through each position, it recursively validates if combinations up to that point are within the allowable range, incrementing the valid count as appropriate.
Python
JavaScript
Time Complexity: O((log n) * m)
Space Complexity: O(log n)
This approach uses dynamic programming to pre-compute the number of valid numbers at each digit position. It updates a dp array to track possible numbers we can form up to each digit, considering all combinations of digits in the set.
In this C++ solution, the function uses a dp array to keep track of the number of valid integers that can be formed for each position in `n`. The dp array is filled from right to left, considering all possibilities for each digit.
Time Complexity: O(mlog n)
Space Complexity: O(log n)
This problem essentially asks for the number of positive integers that can be generated from the digits in digits within the given range [l, .., r]. The count depends on the number of digits and the value of each digit. We can solve this problem using the Digit DP approach. In Digit DP, the size of the number has little impact on the complexity.
For the range [l, .., r] problem, we generally convert it to the problem of [1, .., r] and then subtract the result of [1, .., l - 1], i.e.,
$
ans = sum_{i=1}^{r} ans_i - sum_{i=1}^{l-1} ans_i
However, for this problem, we only need to find the value for the range [1, .., r].
Here, we use memoization to implement Digit DP. We start searching from the top, get the number of solutions at the bottom, and return the answers layer by layer until we get the final answer from the starting point.
The basic steps are as follows:
We convert the number n into a string s and denote the length of the string s as m.
Next, we design a function dfs(i, lead, limit) to represent the number of solutions from the current i-th digit to the last digit of the string. Here:
represents the current position in the string s. indicates whether the current number contains only leading zeros. indicates whether the current position is restricted by the upper bound.The function executes as follows:
If i is greater than or equal to m, it means we have processed all digits. If lead is true, it means the current number is a leading zero, and we should return 0. Otherwise, we should return 1.
Otherwise, we calculate the upper bound up. If limit is true, then up is the digit corresponding to s[i]. Otherwise, up is 9.
Then, we enumerate the current digit j in the range [0, up]. If j is 0 and lead is true, we recursively calculate dfs(i + 1, true, limit \wedge j = up). Otherwise, if j is in digits, we recursively calculate dfs(i + 1, false, limit \wedge j = up). We accumulate all the results as the answer.
Finally, we return dfs(0, true, true).
The time complexity is O(log n times D), and the space complexity is O(log n). Here, D = 10$.
Similar problems:
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Backtracking Approach | Time Complexity: O((log n) * m) |
| Dynamic Programming Approach | Time Complexity: O(mlog n) |
| Digit DP | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking Enumeration | O(k^d) | O(d) | When exploring the search space conceptually or when N is small |
| Digit Dynamic Programming / Combinatorics | O(d * k) | O(1) | General case and interview solution for large N |
Numbers At Most N Given Digit Set 🔥| Leetcode 902 | Math • Ayushi Sharma • 2,574 views views
Watch 9 more video solutions →Practice Numbers At Most N Given Digit Set with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor