3032. Count Numbers With Unique Digits II


Problem Description

This problem requires finding the number of integers between two positive integers a and b (inclusive) that have unique digits. An integer has unique digits if no digit is repeated within that integer. For example, '123' has unique digits, but '112' does not because the digit '1' is repeated.

The challenge lies in efficiently calculating this number over a potentially large range without having to check every integer individually. This problem can be approached algorithmically with combinatory and dynamic programming principles to avoid brute force enumeration, which would be computationally expensive.

Intuition

To intuitively approach this problem, we can think of it in terms of counting. If we need to count the number of unique digit numbers within a range, it's logical to break down the range into smaller parts that are easier to handle. If we count from '1' to the upper bound 'b' and from '1' to 'a-1' and find the difference, we can effectively count the unique digit numbers between 'a' and 'b'.

Now, we can take advantage of digit dynamic programming (digit DP), which often involves solving number-related problems by considering one digit at a time, generally moving from the most significant digit to the least significant digit. This is combined with state compression, which efficiently tracks the state of our computation, particularly which digits have been used so far.

Digit DP can help us on two levels:

  1. It reduces the problem from considering ranges of numbers to considering actual digits, which is a significantly smaller sample space.
  2. The use of memoization prevents us from recalculating states that we've previously solved, which significantly speeds up our computations.

The binary representation of the digit states (state compression) allows us to use bitwise operations to track which digits have been used, allowing us to easily check if adding a new digit would violate the uniqueness condition.

In essence, we use recursion with memoization to count unique digit numbers by building them digit by digit, ensuring that we do not reuse any digits. Our recursive function, dfs, keeps track of which digits are used and whether we are bounded by the current digit of our limit (either 'a - 1' or 'b') at every recursive call. The tricky part is to handle this current digit bounding correctly, which we do with the limit flag.

By comparing the count for the upper and lower bounds, we determine the count of unique digit numbers in the specified range. This approach eliminates the need to explicitly check every number in the range and allows us to solve the problem with greater efficiency.

Learn more about Math and Dynamic Programming patterns.

Solution Approach

The solution provided employs state compression and digit DP to efficiently solve the problem. Here's a step-by-step breakdown of the algorithms and patterns used in the implementation, which will help us understand the approach mentioned in the reference solution:

  1. Converting to String for Easy Digit Access: We start by converting the integer representation of our bounds 'a-1' and 'b' into string format. This allows us to easily access each digit without the need for additional calculations or conversions.

  2. Digit Dynamic Programming (DP): We create a recursive function dfs(pos, mask, limit) that explores each digit position pos of our current number. The mask argument is an integer with bits representing digits used in our current recursive path (state compression). The limit flag tells us if we need to be bound by the digit at the current position, ensuring we do not exceed our upper bound limits.

  3. Memoization and Caching: By leveraging the cache decorator, we can store the results of calculations we've already performed. This significantly reduces the number of computations by eliminating redundant calculations, essential for the overall efficiency of recursive algorithms.

  4. Implementing the Function for Bounds: We compute the count of unique digit numbers upto 'b' by calling dfs(0, 0, True) on the string representation of 'b'. Similarly, we calculate the count upto 'a - 1'. Subtracting these two values yields the answer.

  5. Bitwise Operations for State Compression: In mask, we use bitwise operations to check whether a digit is used (mask >> i & 1) and to update the used digits (mask | 1 << i). This is the essence of state compression: representing the state of used digits with bits in an integer.

  6. Limit Management: While exploring digits, we need to manage the limit to know if we are bound by the current digit of our upper bound. If limit is True, we can only explore digits up to num[pos]. If limit is False, there are no such restrictions. When we opt for a digit equal to num[pos], the subsequent recursive call will still have limit as True.

As a result of this approach, we have a powerful and efficient solution that doesn't directly inspect each number in the range but instead builds potential numbers digit by digit while abiding by the constraints. This greatly cuts down the search space and optimizes calculation times to solve even large input ranges in a reasonable timeframe.

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

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Example Walkthrough

Let's walk through an example to illustrate the solution approach described. Suppose we are trying to find the number of unique digit integers between a=100 and b=130, inclusive.

  1. Converting to String for Easy Digit Access: First, we convert our integer bounds a-1 and b to strings. Hence a-1 becomes '99' and b becomes '130'.

  2. Digit Dynamic Programming (DP): We use a recursive function dfs(pos, mask, limit) where pos starts at 0 (most significant digit), mask starts as 0 (no digits used), and limit starts as True to respect the boundary.

  3. Memoization and Caching: Assume we have a memory cache to store results from the dfs calls indexed by pos, mask, and limit. We do this to not repeat calculations.

  4. Implementing the Function for Bounds: We run the dfs function twice: once up to '99' (representing a-1) and once up to '130' (representing b). We'll store the results as variables, say count_upto_a_minus_1 and count_upto_b.

  5. Bitwise Operations for State Compression: As we build numbers in dfs, say we want to use digit '1', we check if it's already been used with (mask >> 1) & 1. If not, we use it and update the mask to mask | (1 << 1).

  6. Limit Management: If at any pos the limit is True, we can only use digits up to the same digit in our bound ('1', '3', or '0' for '130'). If limit is False, we can use any digit from 0 to 9, provided we haven't used it before.

To calculate the result, we let the algorithm run and simulate using the smaller example below:

  • For '99', the dfs might explore making the first digit '0' through '9' recursively, keeping track of used digits and limits.
  • Once done with '99', we have the count of unique number integers up to 99.
  • For '130', the dfs must start with '1' (since limit is True and '1' is the most significant digit of the upper bound) and can then explore '0' through '3' for the second digit and '0' for the last digit due to the limit flag.
  • Any recursive call that leads to a digit already used in mask will return 0, disallowing repeated digits.

By subtracting count_upto_a_minus_1 from count_upto_b, we get the count of unique digit numbers between 100 and 130, which is our desired answer. In this case, these numbers would be 102, 103, 104, ..., up to 130, except for 110, 120, and 122 through 129 because these numbers contain repeated digits. The dfs function checks all possibilities in a reduced space instead of checking every number individually, which makes it efficient.

Solution Implementation

1from functools import lru_cache  # Import lru_cache for memoization
2
3class Solution:
4    def numberCount(self, a: int, b: int) -> int:
5        # Helper function to perform a depth-first search
6        # pos: current position in the number
7        # mask: bitmask representing which digits have been used
8        # limit: flag to indicate whether the current digit is limited by the input number
9        @lru_cache(maxsize=None)  # Use lru_cache for memoization
10        def dfs(pos: int, mask: int, limit: bool) -> int:
11            # Base case: if we've processed all digits
12            if pos >= len(number_str):
13                # If the mask is 0 (no digit is used), we return 0, otherwise we return 1
14                return 1 if mask else 0
15
16            # Get the upper bound for the current digit
17            upper_bound = int(number_str[pos]) if limit else 9
18            count = 0  # Initialize count of valid numbers
19
20            # Try all possible digits from 0 to the upper_bound
21            for digit in range(upper_bound + 1):
22                # If the digit has already been used, skip it
23                if mask >> digit & 1:
24                    continue
25
26                # Calculate the next mask after including this digit
27                next_mask = (mask | (1 << digit)) if mask != 0 or digit != 0 else 0
28
29                # Increment count by the number of valid numbers starting with this digit
30                count += dfs(pos + 1, next_mask, limit and digit == upper_bound)
31            return count  # Return the total count for this branch
32
33        # Convert integer a-1 to string to prepare for DFS and calculate count for numbers < a
34        number_str = str(a - 1)
35        count_for_a_less_1 = dfs(0, 0, True)  # Count numbers less than 'a'
36        dfs.cache_clear()  # Clear the memoization cache
37
38        # Convert integer b to string to prepare for DFS and calculate count for numbers <= b
39        number_str = str(b)
40        count_for_b = dfs(0, 0, True)  # Count numbers less than or equal to 'b'
41
42        # Return the final count of valid numbers within the range [a, b]
43        return count_for_b - count_for_a_less_1
44
45# Example usage:
46# sol = Solution()
47# print(sol.numberCount(100, 300))  # Output: the count of numbers with unique digits in the range [100, 300]
48
1class Solution {
2    private String numStr;
3    private Integer[][] memoTable;
4
5    // Main method to get the count of unique numbers between a and b
6    public int numberCount(int a, int b) {
7        // Prepare for calculation from a-1, to include a in final count
8        numStr = String.valueOf(a - 1);
9        memoTable = new Integer[numStr.length()][1 << 10];
10        int countUntilA = dfs(0, 0, true);
11      
12        // Prepare for calculation up to b, to include b in final count
13        numStr = String.valueOf(b);
14        memoTable = new Integer[numStr.length()][1 << 10];
15        int countUntilB = dfs(0, 0, true);
16      
17        // Return the count difference, which is the count for [a, b]
18        return countUntilB - countUntilA;
19    }
20
21    // Depth-first search to explore all numbers from 0 up to the target number
22    private int dfs(int position, int mask, boolean isLimited) {
23        // Base case: when reaching the length of numStr, counts 1 if any digit has occurred, 0 if none
24        if (position >= numStr.length()) {
25            return mask > 0 ? 1 : 0;
26        }
27        // If not limited and the answer is cached, return it
28        if (!isLimited && memoTable[position][mask] != null) {
29            return memoTable[position][mask];
30        }
31      
32        // Determine the upper limit for the current digit
33        int upperLimit = isLimited ? numStr.charAt(position) - '0' : 9;
34        int count = 0;
35      
36        // Iterate over all possible digits for current position
37        for (int digit = 0; digit <= upperLimit; ++digit) {
38            // Skip if the digit is already used (mask check)
39            if ((mask >> digit & 1) == 1) {
40                continue;
41            }
42          
43            // Set the next mask
44            int nextMask = mask == 0 && digit == 0 ? 0 : mask | (1 << digit);
45            // Move to the next position, update limit condition
46            count += dfs(position + 1, nextMask, isLimited && digit == upperLimit);
47        }
48      
49        // If the limit flag isn't set, store the computed answer in memoization table
50        if (!isLimited) {
51            memoTable[position][mask] = count;
52        }
53      
54        return count;
55    }
56}
57
1#include <cstring>
2#include <string>
3#include <functional>
4using namespace std;
5
6class Solution {
7public:
8    int numberCount(int a, int b) {
9        // Convert the upper limit of the range into a string
10        string num = to_string(b);
11        // Cache for dynamic programming, initialized to -1
12        int cache[num.size()][1 << 10];
13        memset(cache, -1, sizeof(cache));
14
15        // Recursive function to count the number of unique digit numbers
16        function<int(int, int, bool)> countUniqueDigits = [&](int position, int mask, bool isLimited) {
17            // Base case: If we have reached the end of the number
18            if (position >= num.size()) {
19                return mask ? 1 : 0; // Return 1 if mask is non-zero, else 0
20            }
21            // If we're not limited and the value is already computed, return it
22            if (!isLimited && cache[position][mask] != -1) {
23                return cache[position][mask];
24            }
25            // If we are limited, the upper bound is the current digit in num
26            // Otherwise, it's 9 (since we can choose any digit)
27            int upperBound = isLimited ? num[position] - '0' : 9;
28            int count = 0; // This variable will store the count for this call
29
30            // Iterate over all possible digit choices
31            for (int i = 0; i <= upperBound; ++i) {
32                // Skip if the mask already contains the digit
33                if (mask >> i & 1) {
34                    continue;
35                }
36                // Add the current digit to mask if it is not a leading zero
37                int nextMask = mask == 0 && i == 0 ? 0 : mask | (1 << i);
38                // Recurse with the next position and the updated mask
39                count += countUniqueDigits(position + 1, nextMask, isLimited && i == upperBound);
40            }
41            // Cache the result if we're not limited by the current upper bound
42            if (!isLimited) {
43                cache[position][mask] = count;
44            }
45            return count; // Return the count of unique digit numbers
46        };
47
48        // Initial call with b as the upper limit
49        int upperLimitCount = countUniqueDigits(0, 0, true);
50        // Convert the lower limit of the range into a string
51        // We subtract 1 from 'a' to calculate the count up to 'a - 1'
52        num = to_string(a - 1);
53        // Reset the cache before another pass
54        memset(cache, -1, sizeof(cache));
55        // Recursive call with 'a - 1' as the upper limit
56        int lowerLimitCount = countUniqueDigits(0, 0, true);
57
58        // The result is the numbers with unique digits between 'a - 1' and 'b'
59        return upperLimitCount - lowerLimitCount;
60    }
61};
62
1function numberCount(lowerBound: number, upperBound: number): number {
2    // Convert upper bound to a string to easily access each digit
3    let upperStr: string = upperBound.toString();
4
5    // Memoization table to store the results of subproblems ('f')
6    // Initialized with -1 which signifies that the value hasn't been computed yet
7    const memo: number[][] = Array(upperStr.length)
8        .fill(0)
9        .map(() => Array(1 << 10).fill(-1));
10
11    // dfs is the depth-first-search function that computes the count recursively
12    const dfs: (index: number, usedDigitsMask: number, isLimit: boolean) => number = (index, usedDigitsMask, isLimit) => {
13        // Base case: if we have considered all the digits
14        if (index >= upperStr.length) {
15            return usedDigitsMask ? 1 : 0;
16        }
17        // Use already computed result if there is no limit and it's stored in 'memo'
18        if (!isLimit && memo[index][usedDigitsMask] !== -1) {
19            return memo[index][usedDigitsMask];
20        }
21
22        // Decide the upper limit of the digit that can be placed at current position
23        const digitUpperLimit: number = isLimit ? +upperStr[index] : 9;
24        let totalCount: number = 0;
25
26        // Try all possible digits at the current index position
27        for (let digit = 0; digit <= digitUpperLimit; digit++) {
28            // Skip if the digit is already used (using bitwise 'usedDigitsMask')
29            if ((usedDigitsMask >> digit) & 1) {
30                continue;
31            }
32
33            // Set the digit as used for next recursive calls
34            let nextMask: number = usedDigitsMask | (1 << digit);
35
36            // Special case for leading zero not contributing to the 'usedDigitsMask'
37            if (usedDigitsMask === 0 && digit === 0) {
38                nextMask = 0;
39            }
40
41            // Increment totalCount with recursive call result, and forward the 'isLimit' flag if we are at the limit
42            totalCount += dfs(index + 1, nextMask, isLimit && digit === digitUpperLimit);
43        }
44        // If we are not at the limit, store the computed result in 'memo'
45        if (!isLimit) {
46            memo[index][usedDigitsMask] = totalCount;
47        }
48        return totalCount;
49    };
50
51    // Count of numbers without duplicate digits in the range from 0 to upperBound
52    const countUpper: number = dfs(0, 0, true);
53
54    // Convert lower bound to a string for processing
55    upperStr = (lowerBound - 1).toString();
56
57    // Reset the memo table before computing for the lower bound
58    memo.forEach(row => row.fill(-1));
59
60    // Count of numbers without duplicate digits in the range from 0 to lowerBound - 1
61    const countLower: number = dfs(0, 0, true);
62
63    // The result is the difference of the two counts
64    return countUpper - countLower;
65}
66

Time and Space Complexity

The given code defines a function numberCount that computes the count of numbers between two integers a and b such that no digit repeats within those numbers.

  • Time Complexity:

    The time complexity is derived from the number of recursive calls made by the function dfs. Here m represents the number of digits in the larger number b. For each digit position, there are up to 10 possible digits to choose from (0 through 9). The mask parameter can represent any combination of the 10 digits, meaning there are 2^10 possible mask values. As the recursion can happen for each position of the digit with each possible combination of the masks, and for each digit choice, the total number of calls is in the worst case O(m * 2^10 * 10).

    The constraint limit ensures that we are only considering valid numbers less than or equal to b. Whenever limit is True, it means the current number we are forming has to be less than or equal to the corresponding digits in b. If limit becomes False, we can use any digit at the current position, up to 9. This doesn't affect the worst case scenario much, since the number of operations is still bounded by the number of digits in b and the possible states of the mask.

  • Space Complexity:

    The space complexity is mostly influenced by the space needed to store the results of the recursive calls, which is the memoization cache that the @cache decorator creates. The maximum depth of the recursion is m, which is the number of digits in b. At each level, there can be 2^10 different states of the mask. Therefore, the space needed to store the intermediate results is O(m * 2^10).

In conclusion, the time complexity is O(m * 2^10 * 10) and the space complexity is O(m * 2^10).

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


Fast Track Your Learning with Our Quick Skills Quiz:

Depth first search is equivalent to which of the tree traversal order?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄