Numbers At Most N Given Digit Set
Last Updated: March 28, 2026
Understanding the Problem
We are given a set of allowed digits (each between '1' and '9'), and we need to count how many positive integers up to n can be formed using only those digits. Each digit can be reused as many times as we want. So if digits = ["1","3"], we can form 1, 3, 11, 13, 31, 33, 111, 113, and so on.
The key insight is that this is really a counting problem with two distinct parts. First, any number with fewer digits than n is automatically less than n, so we can count all of those easily. Second, for numbers with the same number of digits as n, we need to carefully count only those that do not exceed n. This second part is where the problem gets interesting, and it is a classic application of digit dynamic programming.
Key Constraints:
1 <= n <= 10^9→ n has at most 10 digits. Any approach that processes digit-by-digit is very efficient.1 <= digits.length <= 9→ The digit set is small. We can iterate over it freely at each position.digits[i]is from'1'to'9'→ No zero in the digit set. This simplifies things because every combination of allowed digits forms a valid positive integer (no leading zero issues).
Approach 1: Brute Force (Enumerate All Numbers)
Intuition
The simplest approach is to generate every possible number from the allowed digits and check if it is at most n. We can do this with BFS: start with each allowed digit, then repeatedly append allowed digits to build longer numbers.
This is straightforward but extremely slow for large n. If digits = ["1","3","5","7"] and n = 10^9, we could potentially generate millions of numbers.
Algorithm
- Start a counter at 0.
- Use a queue to generate numbers starting from each digit in the set.
- For each generated number, if it is at most n, increment the counter and try appending each allowed digit to generate longer numbers.
- If a number exceeds n, stop expanding from it.
- Return the counter.
Code
- Time Complexity: O(answer). We generate every valid number up to n. In the worst case (9 allowed digits, n = 10^9), this can be hundreds of millions of numbers.
- Space Complexity: O(answer). The BFS queue can hold a large number of entries at any point during execution.
This approach generates every valid number, which is far too slow for large inputs. Instead of enumerating, can we count valid numbers mathematically?
Approach 2: Math (Counting by Number of Digits)
Intuition
Instead of generating numbers one by one, we can count them mathematically. The key observation splits the problem into two parts.
Part 1: Numbers with fewer digits than n. If n has L digits, then any valid number with 1 digit, 2 digits, ..., or L-1 digits is automatically less than n. For k-digit numbers, each of the k positions can be any of the d allowed digits (since none of them is '0', there is no leading-zero issue). So there are d^k valid numbers of exactly k digits.
Part 2: Numbers with exactly L digits. We process the digits of n from left to right. At each position i, we ask: how many allowed digits are strictly less than n's digit at position i? Each of those lets us fill the remaining positions freely. Is n's digit at position i itself in the allowed set? If yes, we match it and continue. If no, we stop.
If we successfully match every digit of n, then n itself is a valid number, so we add 1.
We are partitioning all valid numbers into non-overlapping groups. First, we count all numbers that are shorter than n, which are automatically smaller. Then for same-length numbers, we sweep from the most significant digit to the least. At each position, numbers that have already "committed" to being smaller (by choosing a smaller digit at some position) can freely fill the remaining positions. Numbers that match n's digit exactly remain "tied" and need further examination. This is the fundamental principle behind digit counting problems.
Algorithm
- Convert n to a string S of length L. Let d = digits.length.
- Initialize count = 0.
- For k from 1 to L-1, add d^k to count. These are all valid numbers shorter than n.
- For each position i from 0 to L-1:
- Count how many digits in the allowed set are strictly less than S[i]. Call this
less. - Add
less * d^(L-1-i)to count. - If S[i] is not in the allowed set, stop.
- If S[i] is in the allowed set, continue to the next position.
- If we processed all L positions without stopping, add 1 (the number n itself is valid).
- Return count.
Example Walkthrough
Code
- Time Complexity: O(L * D). L is the number of digits in n (at most 10), D is the size of the digit set (at most 9). We do a constant amount of work per (position, digit) pair.
- Space Complexity: O(L). We store the string representation of n. Everything else uses constant space.
This approach uses floating-point Math.pow which can cause precision issues. Can we precompute powers with integer arithmetic and express the solution as a clean DP?
Approach 3: Digit DP (Optimal)
Intuition
We can reformulate this as a dynamic programming problem that processes n from right to left. Define dp[i] as the number of valid numbers that can be formed considering positions i through L-1 of n, under the constraint that the prefix so far exactly matches n.
The recurrence works as follows: for each allowed digit less than S[i], we can fill the remaining positions freely (contributing d^(L-1-i)). For each allowed digit equal to S[i], the answer depends on dp[i+1]. Digits greater than S[i] contribute nothing.
The base case is dp[L] = 1, meaning if we have matched all digits of n exactly, we count n itself. We still add the counts for numbers shorter than n separately.
The DP formulation captures the exact same logic as Approach 2 but in a cleaner, more formal structure. The key insight is that dp[i] represents the number of valid completions from position i onward, given that positions 0 through i-1 have exactly matched n. When a digit is smaller than S[i], all subsequent positions are unconstrained, giving d^(L-1-i) choices. When it equals S[i], the constraint carries forward, captured by dp[i+1]. This bottom-up formulation avoids floating-point arithmetic entirely and makes the logic easy to verify.
Algorithm
- Convert n to string S of length L. Let d = digits.length.
- Precompute powers:
pow[i] = d^ifor i from 0 to L using integer arithmetic. - Compute dp from right to left:
dp[L] = 1(base case: matched all digits of n).- For i from L-1 down to 0:
- For each allowed digit less than S[i]: add
pow[L-1-i]. - For each allowed digit equal to S[i]: add
dp[i+1]. - The answer for same-length numbers is
dp[0]. - Add shorter numbers: sum of
pow[1]throughpow[L-1]. - Return the total.
Example Walkthrough
Code
- Time Complexity: O(L * D). L is the number of digits in n (at most 10), D is the size of the digit set (at most 9). We iterate through each position and each digit once.
- Space Complexity: O(L). We use arrays of size L+1 for the DP table and precomputed powers.