1012. Numbers With Repeated Digits

HardMathDynamic Programming
Leetcode Link

Problem Description

Given an integer n, the task is to count all the positive integers in the range [1, n] that have at least one repeated digit. This means that you have to find number of integers within this range which contain at least one digit that appears more than once.

For example, if n is 20, there's only one number with repeated digits - 11. If n is 100, the numbers with repeated digits are 11, 22, 33, ..., 99, leading to a total of 9.

Intuition

The intuition behind the solution is to use a combinatorial approach. Instead of directly counting the numbers with repeated digits, the solution codes for the complementary count – the number of integers without any repeated digits, and subtracts this count from n to get the final answer.

To count the numbers without repeated digits, a depth-first search (DFS) algorithm is utilized. The primary idea is to traverse each position from the most significant digit to the least significant digit, picking digits that have not yet been used, which ensures there are no repetitions.

The solution involves several key steps:

  1. Calculate the number of unique-digit numbers within the boundary given by n.
  2. The DFS is constrained by whether or not the current digit being chosen is leading or trailing zeros, and whether it is at the limit (the current digit being selected cannot exceed the corresponding digit in n if the limit flag is True).
  3. Counting the valid numbers is done recursively, where at each call of dfs, you make a choice for the current digit and move onto the next position.
  4. Utilize memoization to avoid repeating sub-problems calculations, which significantly increases efficiency.
  5. Eventually, subtract the count of unique-digit numbers from n to account for the numbers that were excluded due to having repeated digits.

This problem combines understanding the permutation and combination concept with a DFS approach to count the numbers meeting a specific criteria, which in this case is having no digit repeated.

Learn more about Math and Dynamic Programming patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

Solution Approach

The solution provided above uses a depth-first search (DFS) algorithm with memoization to efficiently solve the problem. Here is a breakdown of how the implementation works:

  • The numDupDigitsAtMostN function calculates n - f(n). f(n) computes the count of numbers without repeated digits up to n, so subtracting this from n gives the count of numbers with repeated digits.

  • Function f(n) is a helper function that first converts n into a list of its digits (nums). This allows easy access to individual digits when performing the DFS.

  • dfs is a nested function inside f, which has four parameters:

    1. pos: Current digit position we are filling.
    2. mask: A bit-mask used to track which digits have been used so far. If the i-th bit of mask is set, digit i has already been used.
    3. lead: A boolean indicating if we are still in the leading zeros of the number.
    4. limit: A boolean that checks if the current path is bounded by n. This is True when the current path's digits match exactly with n's digits from the most significant digit to the current position.

  • The base case for the DFS occurs when pos is less than 0, indicating that a valid number has been constructed, and a count (1) is returned if lead is False (which indicates that the number is not just leading zeros). Otherwise, it's not a valid number, and 0 is returned.

  • up determines the upper bound for the current digit that we are trying to fill. If the limit is True, we can only go up to the corresponding digit in n. Otherwise, we can freely choose any digit from 0 to 9.

  • The algorithm iterates over all possible digit choices (i) for the current position. If a digit has been used before (checked by mask >> i & 1), it skips to the next digit.

  • For each digit i, the dfs function is recursively called to process the next digit position with an updated mask. The lead flag is turned off unless i is 0 and we are still in the leading zero part of the number. The limit flag is updated to check if the current digit i is equal to the corresponding digit in n.

  • @cache is a decorator that memoizes the results of the DFS calls. This significantly reduces the computational complexity by storing and reusing the results of subproblems.

  • Finally, the sum of all the calls for each digit forms the total count of unique digit numbers, which when subtracted from n gives the required result.

This algorithm effectively navigates through the set of numbers from 1 to n, pruning the search space by skipping over configurations that would lead to repeated digits. Memoization ensures that recursive calls are not recomputed, resulting in a time-efficient solution.

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

Which of the following problems can be solved with backtracking (select multiple)

Example Walkthrough

Let's illustrate the solution with a smaller example, where n is 32. Our goal is to count numbers with repeated digits within the range [1, 32].

The combinatorial approach begins by counting the complement, that is, numbers with unique digits. Here's a breakdown of what the depth-first search (DFS) would look like:

  1. Extract the digits of n, which yields the list [3, 2].
  2. Start the DFS algorithm from the most significant digit. In this case, it's 3 hence the positions would be considered from 2 down to 0.
  3. The mask initially is 0, meaning no digits have been used, lead is True, and limit is True.
  4. At position 2, we have digits from 1 to 3 as choices (since with the limit, we can't go beyond 3).
    • Picking 1, the next recursive call will have pos set to 1, mask updated with digit 1, lead False and limit False (as we are not limited by n anymore).
    • Picking 2, on the other hand, would have similar updates to the next recursive call, but with mask updated for digit 2.
    • Picking 3 will proceed but now the limit remains True.
  5. At position 1, with choices 0 to 9 for the other cases, but up to 2 if limit is True. Picking a number already reflected in the mask is avoided, which eliminates the chance of repeated digits.
    • For example, with 3 picked first and the limit is still True, the choices would only be 0 to 2 and since 3 is in the mask, it would not be chosen again.
    • If we had started with 1 or 2 at the first position, the final digit could freely be anything from 0 to 9 (excluding the starting digit).
  6. The DFS continues recursively, generating all possible unique digit numbers till the pos is less than 0.
  7. At that point, if the lead is False, the algorithm increments the count by 1.

Let's roughly calculate the unique-digit numbers:

  • Starting with 1: The second digit can be any of 0, 2, or 3, giving us 3 more unique-digit numbers (namely 10, 12, 13).
  • Starting with 2: The second digit options are 0, 1, or 3, yielding another 3 (namely 20, 21, 23).
  • Starting with 3: The second digit can only be 0 or 1 because of the limit, yielding 2 (namely 30, 31).

This sums up to 8 unique digit numbers between 1 and 32 using our DFS and combinatorial rules. Now, we subtract this number from 32 to get the number of non-unique digit numbers, which is 32 - 8 = 24.

Thus, there are 24 numbers within [1, 32] with at least one repeated digit (although for this small n, we can easily verify this by direct enumeration). This example simplified the explanation of the algorithm's logic, specifically the DFS, the use of a mask to handle previously used digits, and the significance of limit to remain within bounds. For larger values of n, the actual implementation would leverage memoization to avoid recomputation of intermediate results.

Solution Implementation

1from functools import cache
2
3class Solution:
4    def numDupDigitsAtMostN(self, n: int) -> int:
5        # Count unique digits numbers up to n
6        return n - self.count_unique_digits_up_to_n(n)
7
8    def count_unique_digits_up_to_n(self, n: int) -> int:
9        # Depth-first search function to count numbers with unique digits.
10        @cache
11        def dfs(position: int, mask: int, is_leading_zero: bool, is_limit: bool) -> int:
12            # Base case: if all digits have been processed, return 1 if any non-lead zero has been placed, otherwise 0.
13            if position < 0:
14                return 0 if is_leading_zero else 1
15
16            # Calculate the upper digit based on the limit flag.
17            upper_digit = digits[position] if is_limit else 9
18            count = 0
19
20            # Iterate through digit options for the current position.
21            for digit in range(upper_digit + 1):
22                # Skip this digit if it has already appeared.
23                if mask >> digit & 1:
24                    continue
25
26                # Handle the case of leading zeros
27                if digit == 0 and is_leading_zero:
28                    count += dfs(position - 1, mask, is_leading_zero, is_limit and digit == upper_digit)
29                # Handle other digits
30                else:
31                    count += dfs(position - 1, mask | 1 << digit, False, is_limit and digit == upper_digit)
32            return count
33
34        # Convert the number to list of digits for easier handling.
35        digits = []
36        while n > 0:
37            digits.append(n % 10)
38            n //= 10
39        digits = digits[::-1]  # Reverse to have digits in correct order.
40
41        # Start DFS from the highest place value, with no digits used, leading zeros allowed, and limiting to the upper bound.
42        return dfs(len(digits) - 1, 0, True, True)
43
1class Solution {
2    private int[] digits = new int[11]; // Array to store individual digits of the number
3    private Integer[][] dp = new Integer[11][1 << 11]; // Memoization array for dynamic programming
4
5    // Calculates the number of non-repeating digit integers up to n.
6    public int numDupDigitsAtMostN(int n) {
7        // Total number minus the number without duplicate digits gives number with duplicates
8        return n - countUniqueDigitNumbers(n);
9    }
10
11    // Transforms the number into digits array and starts the DFS traversal.
12    private int countUniqueDigitNumbers(int n) {
13        int digitIndex = -1;
14        // Decomposing the number into digits and storing them in reverse.
15        while (n > 0) {
16            digits[++digitIndex] = n % 10;
17            n /= 10;
18        }
19        // Begin depth-first search from the highest digit's index position.
20        return dfs(digitIndex, 0, true, true);
21    }
22
23    // Recursive DFS to count unique digit numbers.
24    private int dfs(int pos, int mask, boolean isLeadingZero, boolean isLimit) {
25        if (pos < 0) {
26            // Base case: if not leading zero, then it's a valid unique number.
27            return isLeadingZero ? 0 : 1;
28        }
29        // Check the memoization array if the result is already computed.
30        if (!isLeadingZero && !isLimit && dp[pos][mask] != null) {
31            return dp[pos][mask];
32        }
33        int count = 0;
34        // Upper limit for digit; if there is a limit, use the current digit, otherwise use 9.
35        int upperLimit = isLimit ? digits[pos] : 9;
36        for (int i = 0; i <= upperLimit; ++i) {
37            // Skip if digit i is already used.
38            if ((mask >> i & 1) == 1) continue;
39          
40            // If the current digit is a leading zero, continue DFS with the leading zero flag.
41            if (i == 0 && isLeadingZero) {
42                count += dfs(pos - 1, mask, isLeadingZero, isLimit && i == upperLimit);
43            } else {
44                // Mark the current digit as used and continue DFS.
45                count += dfs(pos - 1, mask | (1 << i), false, isLimit && i == upperLimit);
46            }
47        }
48        // Store the computed result in dp array if not leading zero and not under limit constraint.
49        if (!isLeadingZero && !isLimit) {
50            dp[pos][mask] = count;
51        }
52        // Return the count of unique digit numbers for this DFS branch.
53        return count;
54    }
55}
56
1class Solution {
2public:
3    int numDupDigitsAtMostN(int n) {
4        // Computes the number of unique digits numbers up to n
5        return n - countUniqueDigits(n);
6    }
7
8private:
9    int digitList[11];
10    int memoization[11][1 << 11];
11
12    // Helper function to compute the count of numbers with unique digits
13    int countUniqueDigits(int n) {
14        memset(memoization, -1, sizeof(memoization));
15        int digitCount = -1;
16      
17        // Split the number into its digits
18        while (n > 0) {
19            digitList[++digitCount] = n % 10;
20            n /= 10;
21        }
22      
23        // Start DFS from the most significant digit
24        return dfs(digitCount, 0, true, true);
25    }
26
27    // Depth-first search function to count numbers based on the current state
28    int dfs(int pos, int mask, bool isLeadingZero, bool isBoundary) {
29        if (pos < 0) {
30            // If we have finished processing all positions, return 1 if it's
31            // not a leading zero (valid number), otherwise return 0.
32            return isLeadingZero ? 0 : 1;
33        }
34      
35        // If we have already computed this state, and it's not the leading zero
36        // or at the boundary, return the cached result.
37        if (!isLeadingZero && !isBoundary && memoization[pos][mask] != -1) {
38            return memoization[pos][mask];
39        }
40      
41        int upperBound = isBoundary ? digitList[pos] : 9;
42        int uniqueCount = 0;
43      
44        // Try all possible digits in the current position, with pruning for duplicates
45        for (int digit = 0; digit <= upperBound; ++digit) {
46            // Check if digit has already occurred (i.e., check if the digit-th bit is set)
47            if ((mask >> digit) & 1) {
48                continue; // Skip if the digit is already used
49            }
50          
51            // If leading zero and current digit is zero, do not change mask
52            if (isLeadingZero && digit == 0) {
53                uniqueCount += dfs(pos - 1, mask, isLeadingZero, isBoundary && digit == upperBound);
54            } else {
55                // Set the current digit's bit in mask and turn off leading zero flag
56                uniqueCount += dfs(pos - 1, mask | (1 << digit), false, isBoundary && digit == upperBound);
57            }
58        }
59      
60        // Cache the result if it's not leading zero or at the boundary
61        if (!isLeadingZero && !isBoundary) {
62            memoization[pos][mask] = uniqueCount;
63        }
64      
65        return uniqueCount;
66    }
67};
68
1function numDupDigitsAtMostN(n: number): number {
2    // Calls the helper function f and subtracts its result from n.
3    // This calculates the number of numbers without repeated digits up to n.
4    return n - countUniqueDigitNumbers(n);
5}
6
7function countUniqueDigitNumbers(n: number): number {
8    // Turn the number into an array of digits.
9    const digits: number[] = [];
10    while (n > 0) {
11        digits.push(n % 10);
12        n = Math.floor(n / 10);
13    }
14    digits.reverse(); // Reverse to have most significant digit first
15
16    // Initialize dp (dynamic programming) array to store calculated results.
17    const dp = Array.from({ length: digits.length }, () => Array(1 << 10).fill(-1));
18
19    // Helper function to calculate count using DFS with memoization.
20    const searchUniqueNumbers = (pos: number, mask: number, isLeadingZero: boolean, isLimit: boolean): number => {
21        if (pos === digits.length) {
22            // If there's no leading zero, this is a valid number with unique digits.
23            return isLeadingZero ? 0 : 1;
24        }
25        if (!isLeadingZero && !isLimit && dp[pos][mask] !== -1) {
26            // If result is already computed, return it.
27            return dp[pos][mask];
28        }
29
30        const upperBound = isLimit ? digits[pos] : 9;
31        let count = 0;
32
33        for (let digit = 0; digit <= upperBound; ++digit) {
34            if ((mask >> digit) & 1) {
35                // Skip if 'digit' has already occurred (bit is set in 'mask')
36                continue;
37            }
38
39            let nextMask = isLeadingZero && digit === 0 ? mask : mask | (1 << digit);
40            let nextLimit = isLimit && digit === upperBound;
41
42            // Recursively count unique numbers.
43            count += searchUniqueNumbers(pos + 1, nextMask, isLeadingZero && digit === 0, nextLimit);
44        }
45
46        if (!isLeadingZero && !isLimit) {
47            // Cache the result in dp array if not a leading zero and not at the limit.
48            dp[pos][mask] = count;
49        }
50
51        return count;
52    };
53
54    // Initiate DFS from the most significant digit.
55    return searchUniqueNumbers(0, 0, true, true);
56}
57
Not Sure What to Study? Take the 2-min Quiz

Which of these pictures shows the visit order of a depth-first search?

Time and Space Complexity

The given Python code defines a function numDupDigitsAtMostN which calculates the number of numbers without repeated digits that are less than or equal to N. Inside the function, it uses a helper function f which counts the number of unique digit numbers less than or equal to N. The main work is done in the nested dfs function, which is a depth-first search with memoization (@cache).

Time Complexity:

The depth-first search template dfs explores all the digits of the given number N, which has at most O(logN) digits. For each digit, we try to put up to 10 different digits (0 to 9), but we skip those that have already been used (identified by the mask bitset). This results in a maximum of 10 calls per level of the DFS tree.

However, the limiting factor is the state space for memoization, which includes:

  • pos: the current position being filled, which has O(logN) possibilities (number of digits in N).
  • mask: the bitmask representing which digits have already been used, which has 2^10 (1024) possibilities since there are 10 possible digits.
  • lead: a boolean flag denoting whether we're still leading with zeros, which can be true or false (2 possibilities).
  • limit: a boolean flag denoting whether the current digit is limited by the digit in N, which can be true or false (2 possibilities).

Hence, the total number of states is O(logN * 2^10 * 2 * 2), and since we compute each state only once due to memoization, the time complexity to resolve each state is constant.

Therefore, the overall time complexity of the DFS function is O(logN * 2^10).

Space Complexity:

The space complexity of the code is mainly determined by the space needed for the call stack during the DFS, and the space needed to store memoized results.

  • The call stack usage will be O(logN) due to the depth of recursion.
  • The space required for memoization will directly correspond to the number of distinct states, which we established to be O(logN * 2^10).

Therefore, the overall space complexity is also O(logN * 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:

Which two pointer technique does Quick Sort use?

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching 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.

←
↑TA đŸ‘šâ€đŸ«