1012. Numbers With Repeated Digits
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:
- Calculate the number of unique-digit numbers within the boundary given by
n
. - 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 isTrue
). - 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. - Utilize memoization to avoid repeating sub-problems calculations, which significantly increases efficiency.
- 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.
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 calculatesn - f(n)
.f(n)
computes the count of numbers without repeated digits up ton
, so subtracting this fromn
gives the count of numbers with repeated digits. -
Function
f(n)
is a helper function that first convertsn
into a list of its digits (nums
). This allows easy access to individual digits when performing the DFS. -
dfs
is a nested function insidef
, which has four parameters:pos
: Current digit position we are filling.mask
: A bit-mask used to track which digits have been used so far. If thei
-th bit ofmask
is set, digiti
has already been used.lead
: A boolean indicating if we are still in the leading zeros of the number.limit
: A boolean that checks if the current path is bounded byn
. This isTrue
when the current path's digits match exactly withn
'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 iflead
isFalse
(which indicates that the number is not just leading zeros). Otherwise, it's not a valid number, and0
is returned. -
up
determines the upper bound for the current digit that we are trying to fill. If thelimit
isTrue
, we can only go up to the corresponding digit inn
. 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 bymask >> i & 1
), it skips to the next digit. -
For each digit
i
, thedfs
function is recursively called to process the next digit position with an updatedmask
. Thelead
flag is turned off unlessi
is0
and we are still in the leading zero part of the number. Thelimit
flag is updated to check if the current digiti
is equal to the corresponding digit inn
. -
@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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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:
- Extract the digits of
n
, which yields the list[3, 2]
. - Start the DFS algorithm from the most significant digit. In this case, it's
3
hence the positions would be considered from2
down to0
. - The
mask
initially is0
, meaning no digits have been used,lead
isTrue
, andlimit
isTrue
. - At position
2
, we have digits from1
to3
as choices (since with the limit, we can't go beyond3
).- Picking
1
, the next recursive call will havepos
set to1
,mask
updated with digit1
,lead
False
andlimit
False
(as we are not limited byn
anymore). - Picking
2
, on the other hand, would have similar updates to the next recursive call, but withmask
updated for digit2
. - Picking
3
will proceed but now thelimit
remainsTrue
.
- Picking
- At position
1
, with choices0
to9
for the other cases, but up to2
iflimit
isTrue
. Picking a number already reflected in themask
is avoided, which eliminates the chance of repeated digits.- For example, with
3
picked first and thelimit
is stillTrue
, the choices would only be0
to2
and since3
is in themask
, it would not be chosen again. - If we had started with
1
or2
at the first position, the final digit could freely be anything from0
to9
(excluding the starting digit).
- For example, with
- The DFS continues recursively, generating all possible unique digit numbers till the
pos
is less than0
. - At that point, if the
lead
isFalse
, the algorithm increments the count by1
.
Let's roughly calculate the unique-digit numbers:
- Starting with
1
: The second digit can be any of0
,2
, or3
, giving us 3 more unique-digit numbers (namely10
,12
,13
). - Starting with
2
: The second digit options are0
,1
, or3
, yielding another 3 (namely20
,21
,23
). - Starting with
3
: The second digit can only be0
or1
because of the limit, yielding 2 (namely30
,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
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 inN
). - 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.
What's the relationship between a tree and a graph?
Recommended Readings
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
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 Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.