Sponsored
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.
Time Complexity: O((log n) * m)
Space Complexity: O(log n)
1def atMostNGivenDigitSet(digits, n):
2 str_n = str(n)
3 L = len(str_n)
4 count = 0
5 # Count numbers with length less than that of n
6 for i in range(1, L):
7 count += len(digits) ** i
8
9 # Count numbers with the same length as n
10 def backtrack(pos, isTight):
11 if pos == L:
12 return 1
13 validNumbers = 0
14 for digit in digits:
15 if digit < str_n[pos]:
16 validNumbers += len(digits) ** (L - pos - 1)
17 elif digit == str_n[pos]:
18 validNumbers += backtrack(pos + 1, True)
19 return validNumbers
20 count += backtrack(0, True)
21 return count
22
23digits = ['1', '3', '5', '7']
24n = 100
25print(atMostNGivenDigitSet(digits, n))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.
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.
Time Complexity: O(mlog n)
Space Complexity: O(log n)
1import java.util.*;
2
3
This Java solution implements a similar strategy using dynamic programming. The dp array is utilized to calculate and store valid numbers incrementally for each digit level.