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 <= 109In #902 Numbers At Most N Given Digit Set, the goal is to count how many numbers can be formed using a given digit set such that the resulting number is less than or equal to N. A common strategy combines combinatorics with a digit-by-digit comparison against the string representation of N.
First, count all valid numbers whose length is smaller than the number of digits in N. These can be computed using simple power-based counting because any digit from the set can occupy each position. For numbers with the same length as N, iterate through each digit of N and determine how many digits from the set are smaller than the current digit. This allows you to count valid prefixes while maintaining the constraint.
Many implementations use binary search to quickly find how many digits in the set are smaller than a target digit. This approach resembles digit dynamic programming and keeps the computation efficient. The time complexity depends on the length of N and the size of the digit set.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Combinatorics + Digit Comparison | O(L * log D) | O(1) |
| Digit DP Variant | O(L * D) | O(L) |
The Code Skool
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)
1def atMostNGivenDigitSet(digits, n):
2 str_n = str(n)
3 L = len(str_n)
4 count = 0
5 # Count numbers with length less than that of n
6 for i in range(1, L):
7 count += len(digits) ** i
8
9 # Count numbers with the same length as n
10 def backtrack(pos, isTight):
11 if pos == L:
12 return 1
13 validNumbers = 0
14 for digit in digits:
15 if digit < str_n[pos]:
16 validNumbers += len(digits) ** (L - pos - 1)
17 elif digit == str_n[pos]:
18 validNumbers += backtrack(pos + 1, True)
19 return validNumbers
20 count += backtrack(0, True)
21 return count
22
23digits = ['1', '3', '5', '7']
24n = 100
25print(atMostNGivenDigitSet(digits, n))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.
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;
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Digit DP helps handle constraints where numbers must stay below a given limit like N. By tracking whether the current prefix already matches N or is smaller, the algorithm can safely count valid combinations without enumerating every number.
Yes, variations of digit counting and digit dynamic programming problems appear in FAANG-style interviews. This problem tests understanding of combinatorics, prefix constraints, and efficient counting techniques.
An array or sorted list of digits is typically used so that binary search can determine how many digits are smaller than a given digit. Converting N to a string also simplifies position-by-position comparisons.
The optimal approach combines combinatorics with digit-by-digit comparison of N. First count numbers with fewer digits than N, then process numbers with the same length by checking how many digits from the set are smaller at each position. This ensures all valid numbers ≤ N are counted efficiently.
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.