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 <= 109This 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.
JavaScript
Time Complexity: O((log n) * m)
Space Complexity: O(log n)
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.
Java
Time Complexity: O(mlog n)
Space Complexity: O(log n)
| Approach | Complexity |
|---|---|
| Backtracking Approach | Time Complexity: O((log n) * m) |
| Dynamic Programming Approach | Time Complexity: O(mlog n) |
How many Leetcode problems Googlers have solved? #sde #google • The Code Skool • 92,673 views views
Watch 9 more video solutions →Practice Numbers At Most N Given Digit Set with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor