902. Numbers At Most N Given Digit Set

HardArrayMathStringBinary SearchDynamic Programming

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:

Decide whether to place a digit at the current position or not.
If we place a digit, check if the digit is in the set of allowed digits.
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:

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.
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).
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.
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.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

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:

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.
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.
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.
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

1from typing import List
2from functools import cache
3
4class Solution:
5    def at_most_n_given_digit_set(self, digits: List[str], n: int) -> int:
6        # Helper function that performs Depth First Search (DFS) to find the count.
7        @cache
8        def dfs(position, is_leading, is_limit):
9            # If the position is less than or equal to 0, check if leading zero is still true.
10            if position <= 0:
11                return int(not is_leading)
12          
13            # Use the upper bound 'a[position]' if limit is true, otherwise default to 9
14            upper_bound = a[position] if is_limit else 9
15            count = 0
16            for i in range(upper_bound + 1):
17                # If the current digit is a leading zero, continue the DFS without changing leading status
18                if i == 0 and is_leading:
19                    count += dfs(position - 1, is_leading, is_limit and i == upper_bound)
20                # If the digit is in our digit set, continue the DFS counting this digit
21                elif i in digit_set:
22                    count += dfs(position - 1, False, is_limit and i == upper_bound)
23            return count
24
25        # Calculate the length of the number 'n' and populate the 'a' array with each digit.
26        length_of_n = 0
27        a = [0] * 12  # Array initialized to store each digit in reverse.
28        digit_set = {int(d) for d in digits}  # Store digits as integers in a set for easy access.
29      
30        # Extract digits of 'n' and store in 'a' starting from 'a[1]'
31        while n:
32            length_of_n += 1
33            a[length_of_n] = n % 10
34            n //= 10
35
36        # Initiate DFS from the most significant digit, indicating we have a leading zero and are limited by 'n'.
37        return dfs(length_of_n, True, True)
38
39# An example call to the function:
40# sol = Solution()
41# print(sol.at_most_n_given_digit_set(["1","3","5","7"], 100))   # This would return the count of numbers <= 100.
42

1class Solution {
2    private int[] digitsArray = new int[12]; // Array to store digits of the number n
3    private int[][] memo = new int[12][2]; // Memoization table for dynamic programming
4    private Set<Integer> digitSet = new HashSet<>(); // Set to store the unique digits
5
6    // Main function to calculate numbers with digits up to n
7    public int atMostNGivenDigitSet(String[] digits, int n) {
8        // Initialize memoization table with -1, which denotes that the values haven't been calculated yet
9        for (int[] row : memo) {
10            Arrays.fill(row, -1);
11        }
12
13        // Fill digitSet with the digits provided in the input
14        for (String digit : digits) {
15            digitSet.add(Integer.parseInt(digit));
16        }
17
18        // Split the number n into its digits and fill digitsArray
19        int length = 0; // Length of the number n in terms of digits
20        while (n > 0) {
21            digitsArray[++length] = n % 10;
22            n /= 10;
23        }
24
25        // Start dynamic programming with depth-first search
26        return dfs(length, 1, true);
27    }
28
29    // Helper DFS method with memoization
30    private int dfs(int position, int isLeading, boolean isLimit) {
31        // Base case: if there are no more digits to process
32        if (position <= 0) {
33            return isLeading ^ 1; // If leading, return 0, else return 1
34        }
35        // Check memo table if answer already computed for this sub-problem
36        if (!isLimit && isLeading != 1 && memo[position][isLeading] != -1) {
37            return memo[position][isLeading];
38        }
39
40        int count = 0; // Counter for valid numbers
41        int upperBound = isLimit ? digitsArray[position] : 9; // Determine upper bound for loop
42      
43        // Loop through all valid digit choices
44        for (int i = 0; i <= upperBound; ++i) {
45            if (i == 0 && isLeading == 1) {
46                // If i = 0 and this is the leading digit, do not add i to the sequence yet
47                count += dfs(position - 1, isLeading, isLimit && i == upperBound);
48            } else if (digitSet.contains(i)) {
49                // If the digit is in the given set, include it and continue
50                count += dfs(position - 1, 0, isLimit && i == upperBound);
51            }
52        }
53
54        // Cache results in the memo table if not at a limit and not a leading zero
55        if (!isLimit && isLeading == 0) {
56            memo[position][isLeading] = count;
57        }
58        return count; // Return the total count of valid numbers
59    }
60}
61

1class Solution {
2public:
3    int digitsArray[12]; // Array to store each digit of the number 'n'
4    int memoization[12][2]; // Memoization array for the dynamic programming approach
5    unordered_set<int> digitSet; // Set to store the given digits for easy lookup
6
7    // Calculate the number of integers that are less than or equal to n and 
8    // can be formed using the given digit set
9    int atMostNGivenDigitSet(vector<string>& digits, int n) {
10        memset(memoization, -1, sizeof memoization); // Initialize memoization array with -1
11        // Convert strings to integers and add to the set
12        for (auto& d : digits) {
13            digitSet.insert(stoi(d));
14        }
15      
16        int numSize = 0; // Length of the number 'n'
17        // Split the number 'n' into its digits and store in reverse order in the array
18        while (n) {
19            digitsArray[++numSize] = n % 10;
20            n /= 10;
21        }
22      
23        // Call the depth-first search function with the position starting from the last digit,
24        // leading flag set to true, and limit flag set to true
25        return dfs(numSize, 1, true);
26    }
27
28    // Depth-first search function to count the number of valid integers
29    int dfs(int position, int isLeadingZero, bool isLimited) {
30        // Base case: when all positions have been processed
31        if (position == 0) {
32            return isLeadingZero ^ 1; // if isLeadingZero is true, return 0; otherwise, return 1
33        }
34      
35        // If not limited and not leading with zero and value is already computed, return the stored value
36        if (!isLimited && !isLeadingZero && memoization[position][isLeadingZero] != -1) {
37            return memoization[position][isLeadingZero];
38        }
39      
40        int count = 0; // Initialize count of valid numbers
41        int upperBound = isLimited ? digitsArray[position] : 9; // Determine the upper bound for the current digit position
42      
43        // Loop through all possible digits from 0 to the upper bound
44        for (int digit = 0; digit <= upperBound; ++digit) {
45            // Case for leading zero
46            if (digit == 0 && isLeadingZero) {
47                count += dfs(position - 1, isLeadingZero, isLimited && digit == upperBound);
48            }
49            // Case for valid digit from the set
50            else if (digitSet.count(digit)) {
51                count += dfs(position - 1, 0, isLimited && digit == upperBound);
52            }
53        }
54      
55        // Store the result in memoization array if the case is not limited and does not have leading zero
56        if (!isLimited && !isLeadingZero) {
57            memoization[position][isLeadingZero] = count;
58        }
59      
60        return count; // Return the total count of valid numbers
61    }
62};
63

1// We'll define the relevant types and variables globally.
2
3type MemoizationArray = number[][];
4let digitsArray: number[] = new Array(12); // Array to store each digit of the number 'n'
5let memoization: MemoizationArray = Array.from(Array(12), () => Array(2).fill(-1)); // 2D array for memoization
6let digitSet: Set<number> = new Set<number>(); // Set to store the given digits for easy lookup
7
8// Calculate the number of integers that are less than or equal to n and
9// can be formed using the given digit set.
10function atMostNGivenDigitSet(digits: string[], n: number): number {
11    // Reset memoization array with -1
12    memoization = memoization.map(row => row.fill(-1));
13  
14    // Convert strings to integers and add to the set
15    digits.forEach(d => digitSet.add(parseInt(d)));
16  
17    let numSize: number = 0; // Length of the number 'n'
18  
19    // Split the number 'n' into its digits and store in reverse order in the array
20    while (n) {
21        digitsArray[++numSize] = n % 10;
22        n = Math.floor(n / 10);
23    }
24  
25    // Call the depth-first search function with the position starting from the last digit,
26    // leading flag set to true, and limit flag set to true
27    return dfs(numSize, 1, true);
28}
29
30// Depth-first search function to count the number of valid integers
31function dfs(position: number, isLeadingZero: number, isLimited: boolean): number {
32    // Base case: when all positions have been processed
33    if (position === 0) {
34        return isLeadingZero ^ 1;
35    }
36  
37    // If not limited and not leading with zero and value is already computed, return the stored value
38    if (!isLimited && isLeadingZero === 0 && memoization[position][isLeadingZero] !== -1) {
39        return memoization[position][isLeadingZero];
40    }
41  
42    let upperBound: number = isLimited ? digitsArray[position] : 9; // Determine the upper bound for the current digit position
43    let count: number = 0; // Initialize count of valid numbers
44  
45    // Loop through all possible digits from 0 to the upper bound
46    for (let digit = 0; digit <= upperBound; digit++) {
47        // Case for leading zero
48        if (digit === 0 && isLeadingZero) {
49            count += dfs(position - 1, isLeadingZero, isLimited && digit === upperBound);
50        }
51        // Case for valid digit from the set
52        else if (digitSet.has(digit)) {
53            count += dfs(position - 1, 0, isLimited && digit === upperBound);
54        }
55    }
56  
57    // Store the result in memoization array if the case is not limited and does not have leading zero
58    if (!isLimited && isLeadingZero === 0) {
59        memoization[position][isLeadingZero] = count;
60    }
61  
62    return count; // Return the total count of valid numbers
63}
64

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:

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.
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.
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).
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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

You are given an array of intervals where intervals[i] = [start_i, end_i] represent the start and end of the ith interval. You need to merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

Sort the intervals by their start time, then iterate through the sorted intervals, merging any overlapping intervals.

Brute force through all interval combinations and find the answer with the least total intervals.

Iterate through the intervals in their original order, merging any overlapping intervals.

Use a priority queue to keep track of the intervals, merging any overlapping intervals.

I don't know