902. Numbers At Most N Given Digit Set

Problem Description

The problem asks us to determine how many positive integers we can generate that are less than or equal to a given integer n, using the given set of digits. The digits are provided in a non-decreasing array, and you can use each digit as many times as desired to form numbers. For instance, if the digit set is [1, 3, 5], you can form numbers such as 13, 551, and 1351315. Importantly, the numbers we create must be less than or equal to n.

Intuition

The given problem is a classic case of digit dynamic programming (DP) combined with the concept of combinatorial mathematics. The algorithm counts all valid numbers up to the length of n considering the following:

• For each length i smaller than the number of digits in n, we calculate how many distinct numbers can be formed using the available digits.
• To handle the constraint that formed numbers must be less than or equal to n, we compare the generated digits with the corresponding digits of n when we reach the same number of digits as in n.
• If we have a leading zero (which means we haven't started writing digits of the number yet), it's a special case and must be handled differently because we don't count these leading zeros as part of a number.

The recursive function dfs (depth-first search) is used to traverse through the possibilities. We use several parameters for our DFS function:

• pos: Positions left to fill in our number. This can be thought of as the place value we're currently considering.
• lead: A boolean flag indicating whether we have started creating our number or are still at leading zeroes.
• limit: A boolean flag indicating whether we're limited by the digit at our current position of n.

At each recursive call, we:

1. Decide whether to place a digit at the current position or not.
2. If we place a digit, check if the digit is in the set of allowed digits.
3. If we are at the last digit (pos is 1), ensure we do not exceed the corresponding digit of n if limit is True.

Moreover, the algorithm is optimized using memoization (@cache) to avoid recomputations of states that we have already calculated. We build up an answer by counting all the valid combinations recursively, and our base case checks whether we have filled out all the positions and met the conditions.

Learn more about Math, Binary Search and Dynamic Programming patterns.

Solution Approach

In the given solution, we have implemented several important concepts:

1. Depth-First Search (DFS) and Memoization: The dfs function represents a depth-first recursive search with memoization. The memoization is enabled using the @cache decorator which stores the results of previous computations and avoids redundant calculations.

2. Digit-wise Comparison and Computation: We compare each digit of the potential numbers with the corresponding digit in n. This comparison dictates whether we have a limit to follow (if the current digit of the potential number is the same as the one at the corresponding position in n).

3. Handling Leading Zeros: The lead variable serves a dual purpose. Initially, it is True to indicate that we haven't started forming the number (we're at leading zeros). As soon as we place a nonzero digit from our set, we set lead to False. Leading zeros are not counted as part of a number, so they are handled differently.

4. Breaking Down the Problem: The problem is simplified by considering it digit by digit. For each digit position from right to left, we explore all possible digit options from the given set.

Here's a detailed breakdown of the solution implementation:

• The main function atMostNGivenDigitSet begins by initializing a few variables. l will keep track of the length of the number n. a is an array of size 12 (since the constraints of the problem assure n will have at most 10 digits, additional space is for safety). s is a set that stores the digits provided in the digit set (for constant-time access).

• We populate a with the digits of n by progressively dividing n by 10 and storing the remainder. This effectively stores n in a reversed manner (least significant digit first).

• dfs is then called with the position set to the length of n, lead set to True, and limit set to True. The dfs function will now try to compute the count of numbers recursively.

• Inside dfs, we first check the base case: if pos is 0, it means we have already formed our number and check if lead is False (which means we actually started the number and it isn't just leading zeros). If this is the case, we return 1 for a valid number, else 0.

• If not the base case, we then determine the upper bound (up) for the current position. If we are limited by n, up will be the current digit in n. Otherwise, it's 9 (since it's the largest digit we could place).

• We loop through all digits from 0 to up (including up). For each digit, we determine if we can place that digit into our current position either if it's a leading zero (and we still haven't started the number), or if it's a digit from our set. If it's a zero and lead is True, we recursively call dfs with decremented pos, the same lead, and limit updated accordingly (limit and i == up). If it's a digit in our set, lead is set to False.

• We sum up the results and return them, giving a count of all the valid combinations that can form a number less than or equal to n given the constraints.

The code effectively uses a bottom-up approach since it starts from the least significant digit and works its way to the most significant, calculating the number of possibilities at each step and letting the recursion handle the complexity.

Example Walkthrough

To illustrate the solution approach, let's use the digit set [1, 3, 5] and the target integer n = 300.

Walkthrough using the digit set [1, 3, 5]:

• We start by storing the digits of n in reverse order in an array a, which will be [0, 0, 3].
• We initialize our dfs with pos at 3 (the length of n), lead as True (indicating leading zeros), and limit as True (indicating we must respect the digits in n).

Let's begin by running the dfs function:

1. On the first call, dfs(3, True, True), we check digits from 0 to 3 (since 3 is the current digit of n at the position we're at, and we're under limit):

   • Choosing 0 gives us a call to dfs(2, True, True) (still leading zeros).
   • Choosing 1 or 3 sets lead to False and makes recursive calls dfs(2, False, True) and dfs(2, False, False) respectively because we can only match 3 once without a limit.

2. After the above, we proceed with calls like dfs(2, False, True). At position 2, since a[2] is 0, our upper bound is 9 as limit is False now:

   • Again, zeros are skipped and we consider digits 1, 3, and 5 (from our set), making recursive calls dfs(1, False, False) for each since there is no upper bound anymore.

3. Now at the last position with dfs(1, False, False), we have an upper bound of 9, and we can place any digit from our set, resulting in calls dfs(0, False, False) for each selected digit.

4. Once pos reaches 0, we've successfully formed a number without violating any constraints and the base case returns 1 indicating a valid number count. If at any point, a digit choice is not in our digit set, then that branch of the recursive tree does not contribute to the count.

Counting each of these valid calls, we get:

• For dfs(2, True, True), which corresponds to having one leading zero and two positions to fill, only 1 and 3 lead to valid numbers.
• For dfs(1, False, False), all digits 1, 3, and 5 are valid choices for each of the previous positions.

Therefore, for n = 300 with the given set [1, 3, 5]:

• The number of possible numeric combinations of one digit is 3 (since 1, 3, and 5 are all ≤ 3 and 0 doesn't count).
• The number of possible numeric combinations of two digits is 3 * 3 because for each valid single-digit number, we can append any of the digits from the set at the tens place (1X, 3X, and 5X where X can again be 1, 3, or 5).
• For three digits, we initially have the possibility of 1XX or 3XX. We cannot use 5 in the hundreds place because that would exceed 300. So we have an additional 3 * 3 (for 1XX) plus another 3 * 3 (for 3XX) combinations, giving us 18 for this case.

By aggregating these counts, we get a total number of positive integers less than or equal to 300, which can be formed using the digits [1, 3, 5]: the sum is 3 + 9 + 18, amounting to 30.

Solution Implementation

Time and Space Complexity

The given code defines a function atMostNGivenDigitSet which is used to determine the number of valid numbers that can be formed with a given set of digits that are at most N.

To understand the complexity, let’s walk through the main components of the code:

1. dfs is a recursive function that's used to figure out the count of valid numbers of a given length. It's decorated with @cache which memoizes the results of the calls to avoid repeated computation on the same states.

2. dfs function is called with three parameters: pos which denotes the current position in the number we are forming, lead which indicates whether we have already placed a non-zero digit or not, and limit which indicates if we are bound by the upper limit n.

3. Inside dfs, there is a loop that iterates at most 10 times (0 through 9, hence the up + 1 where up is the upper bound digit we can use at the current position).

4. There is post-processing of the value n to convert it into an array a which takes linear time related to the number of digits in n.

Time Complexity: The time complexity of the algorithm is determined by the number of states the dfs can have and how many times each state is computed. With memoization, each state is computed exactly once. The number of states is determined by the pos parameter, which can have l different values (where l is the length of n), the lead parameter, which can be True or False, and the limit parameter, which can also be True or False. This gives us a total of 2 * 2 * l = 4l states. Since the digit loop runs at most 10 times, the time complexity is O(10 * 4l) which simplifies to O(l).

Space Complexity: The space complexity is determined by the depth of the recursion stack and the size of the cache. The deepest the recursion stack can go is l (which is the number of digits in n). The cache size is also 4l states as calculated above. Thus, the overall space complexity is O(l) for the recursion stack plus O(l) for the cache, leading to O(l) space complexity overall.

Learn more about how to find time and space complexity quickly using problem constraints.