Numbers At Most N Given Digit Set
Problem Description
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
Solve it on LeetCode
Approaches
1. Brute Force Enumeration
Intuition:
The brute force method involves generating all possible numbers from the given digit set and checking if they are less than or equal to the target number N. This approach is based on generating permutations of increasing lengths and counting how many are valid.
Steps:
- Convert the integer
Nto a string to easily access individual digits. - Generate all numbers of lengths from 1 up to the length of
Nusing the digits. - For each generated number, check if it is less than or equal to
Nand count it.
Code:
- Time Complexity:
O((D.length)^(log10 N))wherelog10 Nis the number of digits inN. - Space Complexity:
O(log10 N)for the recursive stack.
2. Dynamic Programming with Digit DP
Intuition:
This approach leverages digit dynamic programming to count the valid numbers directly instead of generating and validating them one by one. We pre-compute the numbers using dynamic programming, breaking the problem into manageable sub-problems.
Steps:
- Define a recursive function with memoization to solve for smaller sub-problems.
- Use the DP table to store results of previously computed states.
- Accumulate results from the DP table to get the final count of valid numbers.
Code:
- Time Complexity:
O(nLen * D.length)wherenLenis the number of digits inN. - Space Complexity:
O(nLen * D.length)for memoization table.
3. Mathematical Counting
Intuition:
Instead of generating numbers one-by-one, this approach leverages counting principles. We break down the problem by counting numbers having fewer digits than N and exactly digits of N.
Steps:
- Count numbers of all lengths smaller than the length of
N. - Use prefix-based digit-by-digit comparison to generate valid numbers of the same length as
N. - Accumulate the count based on the above computations.
Code:
- Time Complexity:
O(nLen * D.length)wherenLenis the number of digits inN. - Space Complexity:
O(1)no extra space required beyond variables.