Numbers At Most N Given Digit Set - Video Solutions
Numbers At Most N Given Digit Set π₯| Leetcode 902 | Math
Numbers At Most N Given Digit Set - Video Solution
Watch 10 video solutions for Numbers At Most N Given Digit Set, a hard level problem involving Array, Math, String. This walkthrough by Ayushi Sharma has 2,633 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 9digits[i].length == 1digits[i]is a digit from'1'to'9'.- All the values in
digitsare unique. digitsis 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.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking Enumeration | O(k^d) | O(d) | When exploring the search space conceptually or when N is small |
| Digit Dynamic Programming / Combinatorics | O(d * k) | O(1) | General case and interview solution for large N |