Sponsored
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.
Time Complexity: O((log n) * m)
Space Complexity: O(log n)
1function atMostNGivenDigitSet(digits, n) {
2 const strN = n.toString();
3 const L = strN.length;
4 let count = 0;
5 // Count numbers with length less than that of n
6 for (let i = 1; i < L; i++) {
7 count += Math.pow(digits.length, i);
8 }
9
10 // Count numbers with the same length as n
11 function backtrack(pos, isTight) {
12 if (pos === L) return 1;
13 let validNumbers = 0;
14 for (let digit of digits) {
15 if (digit < strN[pos]) {
16 validNumbers += Math.pow(digits.length, L - pos - 1);
17 } else if (digit === strN[pos]) {
18 validNumbers += backtrack(pos + 1, true);
19 }
20 }
21 return validNumbers;
22 }
23 count += backtrack(0, true);
24 return count;
25}
26
27const digits = ['1', '3', '5', '7'];
28const n = 100;
29console.log(atMostNGivenDigitSet(digits, n));This JavaScript solution mirrors the approach used in Python. It leverages backtracking to explore valid numbers digit-by-digit, counting all combinations of digits less than or equal to the ones in `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.
Time Complexity: O(mlog n)
Space Complexity: O(log n)
1import java.util.*;
2
3
This Java solution implements a similar strategy using dynamic programming. The dp array is utilized to calculate and store valid numbers incrementally for each digit level.