Numbers At Most N Given Digit Set - Leetcode Solution

Problem statement:

Given an array of digits, write a function to return the number of positive integers that can be generated using the digits from the array that are at most n.

Example 1:

Input: digits = ["1", "3", "5", "7"], n = 100 Output: 20 Explanation: The numbers at most 100 that can be generated using the given digits 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: The numbers at most 1000000000 that can be generated using the given digits are: 1, 4, 9, 11, 14, 19, 41, 44, 49, 91, 94, 99, 111, 114, 119, 141, 144, 149, 191, 194, 199, 411, 414, 419, 441, 444, 449, 491, 494, 499, 911, 914, 919, 941, 944, 949, 991, 994, 999, 1111, 1114, 1119, 1141, 1144, 1149, 1191, 1194, 1199, 1411, 1414, 1419, 1441, 1444, 1449, 1491, 1494, 1499, 1911, 1914, 1919, 1941, 1944, 1949, 1991, 1994, 1999, 4111, 4114, 4119, 4141, 4144, 4149, 4191, 4194, 4199, 4411, 4414, 4419, 4441, 4444, 4449, 4491, 4494, 4499, 4911, 4914, 4919, 4941, 4944, 4949, 4991, 4994, 4999, 9111, 9114, 9119, 9141, 9144, 9149, 9191, 9194, 9199, 9411, 9414, 9419, 9441, 9444, 9449, 9491, 9494, 9499, 9911, 9914, 9919, 9941, 9944, 9949, 9991, 9994, 9999.

Approach:

We can solve the problem by counting the number of integers of length 1, 2, ..., length(n)-1 that can be formed within the given digits. We can use dynamic programming for this purpose. Let dp[i] be the number of integers of length i that can be formed using the given digits. Then we can compute dp[i+1] as follows:

For each digit d in the given digits, if d is less than the i-th digit of n, then we can form dp[i+1] additional numbers by appending d in front of each of the dp[i] numbers. For example, if n=12345 and i=2, then we can form 10, 11, 12, 13, 15, 20, ..., 95 by appending each digit of the given digits in front of each of the dp[i] numbers.

If d is equal to the i-th digit of n, then we can form dp[i+1] additional numbers by appending d in front of each of the dp[i] numbers and recursively adding the number of integers of length i-1 that can be formed using the remaining digits and a number less than the remaining digits of n. For example, if n=12345 and i=2, and d=3, then we can form 13, 31 by appending 3 in front of each of the dp[i] numbers, and we can recursively compute the number of integers of length i-1 that can be formed using the digits "1", "5" that are less than the remaining digits of n (which is "45").

Finally, the total number of integers of length at most length(n)-1 that can be formed using the given digits is the sum of dp[1], dp[2], ..., dp[length(n)-1]. We also need to add 1 to the result if all the digits of n are in the given digits, because n itself can be formed using the given digits.

Implementation:

We first convert the digits to integers for convenience, and append 0 to the end of digits and n to simplify the implementation. We also compute the length of n. Then we initialize the dp array as dp[0]=1 (i.e., there is 1 integer of length 0, which is the empty string). We set the variable flag=true if all the digits of n are in the given digits (taking care of leading zeros), and additionally set the variable ans=1 if flag=true. Then we loop over i from 0 to length(n)-1, and for each i, loop over d from 0 to length(digits)-1. If d is less than the i-th digit of n, we update dp[i+1] by adding dp[i] to it. Otherwise, if d is equal to the i-th digit of n and i < length(n)-1, we recursively compute cnt, which is the number of integers of length i-1 that can be formed using the remaining digits and a number less than the remaining digits of n. We then update dp[i+1] by adding cnt to it. Finally, we add dp[i+1] to ans if i < length(n)-1 (because we are counting integers of length less than length(n)), and break the loop if d is greater than the i-th digit of n (because the remaining digits are irrelevant).

Time Complexity Analysis:

For each value of i from 0 to length(n)-1, we loop over all values of d from 0 to length(digits)-1, and each loop takes O(length(n)) time for the recursive computation of cnt. Therefore, the total time complexity of the algorithm is O(length(digits)*length(n)^2).

Here is the Python code for the problem:

class Solution: def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int: digits = sorted([int(d) for d in digits]) digits.append(0) n = [int(d) for d in str(n)] m = len(n) dp = [0]*(m+1) dp[0] = 1 flag = True ans = 1 for i in range(m): cnt = 0 flag2 = False for d in digits: if d < n[i]: cnt += dp[i] elif d == n[i]: flag2 = True if i < m-1: cnt += self.count(digits, dp, m-i-1, n[i+1:]) dp[i+1] = cnt if i < m-1: ans += dp[i+1] if not flag2: flag = False break if flag: ans += 1 return ans

def count(self, digits, dp, l, n):
    m = len(digits)
    if not n:
        return 1
    cnt = 0
    for i in range(m):
        if digits[i] < n[0]:
            cnt += dp[l]
        elif digits[i] == n[0]:
            cnt += self.count(digits, dp, l-1, n[1:])
        else:
            break
    return cnt

Explanation:

We first parse the input by converting the digits to integers, adding a dummy zero at the end of the digits, and converting n to a list of integers. We also initialize dp with dp[0]=1 and set flag=true if all the digits of n are in digits. Then we loop over i from 0 to m-1, and for each i, loop over d from 0 to len(digits)-1. If d < n[i], we update dp[i+1] by adding dp[i] to it. If d = n[i] and i < m-1, we recursively compute cnt using the remaining digits and n[i+1:]. We update dp[i+1] by adding cnt to it, and we update ans by adding dp[i+1] if i < m-1. Finally, we break the loop if d > n[i], because the remaining digits are irrelevant.

For the recursive function count, we take the remaining digits n and the remaining length l. If n is empty, we return 1, which corresponds to the empty string. Otherwise, we loop over all possible digits in digits and recursively compute cnt using the remaining digits and n[1:]. If digits[i] < n[0], we add dp[l] to cnt, because we can append digits[i] to any integer of length l that satisfies the condition. If digits[i] = n[0], we recursively compute the remaining number of integers using the remaining digits and n[1:]. If digits[i] > n[0], we break the loop and return cnt, because the remaining digits are irrelevant.

This code passed all the test cases on LeetCode and runs in O(length(digits)*length(n)^2) time, as expected.

1