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)
1#include <iostream>
2#include <vector>
3#include <string>
4#include <cmath>
5using namespace std;
6
int atMostNGivenDigitSet(vector<string>& digits, int n) {
string str_n = to_string(n);
int L = str_n.size(), m = digits.size();
vector<int> dp(L + 1, 0);
dp[L] = 1;
for (int i = L - 1; i >= 0; --i) {
for (string& d : digits) {
if (d[0] < str_n[i])
dp[i] += pow(m, L - i - 1);
else if (d[0] == str_n[i])
dp[i] += dp[i + 1];
}
}
for (int i = 1; i < L; ++i)
dp[0] += pow(m, i);
return dp[0];
}
int main() {
vector<string> digits = {"1", "3", "5", "7"};
int n = 100;
cout << atMostNGivenDigitSet(digits, n) << endl;
return 0;
}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.