Skip to main content
Talentd

Numbers At Most N Given Digit Set - Solution & Explanation

HardArrayMathStringBinary Search21 min readAsked at: Amazon, Microsoft, Google +1
Practice this problem

Problem Statement

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 <= 9
  • digits[i].length == 1
  • digits[i] is a digit from '1' to '9'.
  • All the values in digits are unique.
  • digits is sorted in non-decreasing order.
  • 1 <= n <= 109

Approach Overview

Problem 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.

Approach 1: Backtracking Approach

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.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O((log n) * m)
Space Complexity: O(log n)

Try this approach in the editor →

Approach 2: Dynamic Programming Approach

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.

Code

C++Java

C++

Java

Complexity

Time Complexity: O(mlog n)
Space Complexity: O(log n)

Try this approach in the editor →

Approach 3: Digit DP

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:

  • The integer i represents the current position in the string s.
  • The boolean lead indicates whether the current number contains only leading zeros.
  • The boolean limit 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:

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Backtracking Approach

Time Complexity: O((log n) * m)
Space Complexity: O(log n)

Dynamic Programming Approach

Time Complexity: O(mlog n)
Space Complexity: O(log n)

Digit DP—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Backtracking EnumerationO(k^d)O(d)When exploring the search space conceptually or when N is small
Digit Dynamic Programming / CombinatoricsO(d * k)O(1)General case and interview solution for large N

Video Solution

Numbers At Most N Given Digit Set 🔥| Leetcode 902 | Math • Ayushi Sharma • 2,633 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Numbers At Most N Given Digit Set easy or hard?
Numbers At Most N Given Digit Set is classified as a hard problem on LeetCode. The difficulty comes from recognizing the digit DP pattern and converting the constraint "≤ N" into prefix-based counting instead of brute-force generation.
Numbers At Most N Given Digit Set Python/Java solution
Python implementations often use recursion or backtracking for the brute-force version, while optimized solutions rely on digit DP logic. Java and C++ implementations typically compute powers of the digit count and iterate through the digits of N to accumulate valid combinations in O(d * k) time.
How to solve Numbers At Most N Given Digit Set in O(n)?
Treat N as a digit string and process it from left to right. First count all numbers with fewer digits using k^length combinations. Then for each digit position, count how many allowed digits are smaller than the current digit of N and add k^(remaining positions). Stop when a digit in N is not available in the digit set. This yields an O(d * k) solution.
What is the best approach for Numbers At Most N Given Digit Set?
Digit dynamic programming combined with combinatorics is the best approach. It counts valid numbers by analyzing each digit position of N and calculating how many prefixes can be formed using the allowed digits. This avoids generating every number explicitly and runs in O(d * k) time, where d is the number of digits in N and k is the size of the digit set.
Is Numbers At Most N Given Digit Set asked at Google/Amazon/Meta?
Digit DP and combinatorial counting problems similar to this one appear in interviews at companies like Google, Amazon, and Meta. They test the ability to reason about digit constraints, prefix comparisons, and dynamic counting rather than brute-force enumeration.
What data structure is used in Numbers At Most N Given Digit Set?
The solution mainly uses arrays or sets to store the allowed digits and string processing for the digits of N. The key technique is digit dynamic programming, which tracks valid prefixes and counts combinations mathematically.
What is the time complexity of Numbers At Most N Given Digit Set?
The optimal digit DP solution runs in O(d * k) time, where d is the number of digits in N and k is the size of the digit set. Space complexity is O(1) because only a few counters and digit comparisons are required. A brute-force backtracking approach can take O(k^d) time.

Ready to solve this problem?

Practice Numbers At Most N Given Digit Set with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays