LeetCode 1012 - Numbers With Repeated Digits
The problem asks us to count how many integers in the range [1, n] contain at least one repeated digit. A repeated digit means that some digit appears more than once in the number. For example, 11 has a repeated 1, 100 has repeated 0, and 121 has repeated 1.
Difficulty: 🔴 Hard
Topics: Math, Dynamic Programming
Solution
Problem Understanding
The problem asks us to count how many integers in the range [1, n] contain at least one repeated digit.
A repeated digit means that some digit appears more than once in the number. For example, 11 has a repeated 1, 100 has repeated 0, and 121 has repeated 1. On the other hand, 123 and 9870 contain only unique digits.
The input is a single integer n, and the output is the count of numbers from 1 through n that contain duplicated digits.
A direct interpretation is:
- Count every integer
xwhere1 <= x <= n - Check whether
xhas any digit appearing more than once - Return the total count
The constraint 1 <= n <= 10^9 is extremely important. Since n can be as large as one billion, iterating through every number and checking its digits would be inefficient in the worst case. A brute-force solution would require processing up to one billion numbers, which is far beyond acceptable runtime limits.
The key observation is that the problem becomes much easier if we count the complement instead. Instead of directly counting numbers with repeated digits, we count numbers with all unique digits, then subtract from n.
Formally:
answer = n - count_of_numbers_with_unique_digits
This transformation is powerful because counting unique-digit numbers can be done efficiently using combinatorics and digit dynamic programming ideas.
Several edge cases are important:
- Small values like
n = 1orn = 9, where no repeated digits exist - Boundary transitions like
10,11,99,100, and101 - Numbers containing repeated zeros, such as
1000 - Numbers where repetition appears late in the digit sequence, such as
123451
The problem guarantees that n is positive, so we never need to handle negative values or empty input.
Approaches
Brute Force Approach
The most straightforward solution is to iterate through every number from 1 to n and check whether the number contains repeated digits.
For each number:
- Convert it into digits
- Use a set to track which digits have already appeared
- If a digit appears twice, increment the answer
This approach is correct because every number is checked independently and exhaustively.
However, the runtime is too slow for large inputs. If n = 10^9, we would potentially process one billion numbers, and each number requires digit extraction and set operations.
Even though checking one number takes only O(log n) time, the total runtime becomes infeasible.
Optimal Approach
The key insight is that counting numbers with unique digits is easier than counting numbers with repeated digits.
Instead of directly counting duplicates, we compute:
repeated = n - unique
To count unique-digit numbers efficiently, we use digit-by-digit construction.
We process the digits of n from left to right and count how many valid numbers can be formed without repeating digits.
The algorithm has two major parts:
- Count all unique-digit numbers with fewer digits than
n - Count unique-digit numbers with the same length as
n
For the second part, we build the number digit by digit while tracking which digits have already been used.
This works because at every position we can determine exactly how many remaining valid choices exist using permutations.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n log n) | O(log n) | Check every number individually |
| Optimal | O((log n)^2) | O(log n) | Uses combinatorics and digit-based counting |
Algorithm Walkthrough
Step 1: Convert n + 1 into digits
We work with n + 1 instead of n because it simplifies inclusive counting.
For example, if n = 100, then processing 101 allows us to count all valid numbers strictly smaller than 101, which is equivalent to counting numbers <= 100.
Step 2: Count unique-digit numbers with fewer digits
Suppose n = 5432.
Before considering 4-digit numbers, we count all unique-digit numbers with:
- 1 digit
- 2 digits
- 3 digits
For length k:
- The first digit cannot be zero
- Remaining digits must be distinct
The count is:
9 × P(9, k - 1)
Where:
9choices for the first digit (1-9)P(9, k - 1)is the permutation count for remaining positions
Example for 3-digit numbers:
9 × 9 × 8 = 648
Step 3: Process numbers with the same length
Now we count valid numbers with exactly the same number of digits as n.
We process digits from left to right.
At each position:
- Try placing a smaller digit than the current digit
- Ensure that digit has not already been used
- Count how many ways the remaining positions can be filled
We maintain a set called used to track digits already chosen.
Step 4: Count permutations for remaining positions
Suppose we are filling a 4-digit number and have already fixed the first two digits.
If there are m remaining unused digits and r remaining positions, then the number of ways is:
P(m, r)
This is computed iteratively.
Step 5: Stop if a repeated digit appears
While processing digits of n, if we encounter a digit already present in used, then the current prefix already contains repetition.
At that point, no further valid unique-digit numbers can be formed, so we stop immediately.
Step 6: Compute final answer
At the end:
answer = n - unique_count
Because:
total numbers = unique-digit numbers + repeated-digit numbers
Why it works
The algorithm systematically counts every valid unique-digit number exactly once.
Numbers with fewer digits are counted separately using permutations. Numbers with the same length are counted digit by digit while preserving the prefix constraint imposed by n.
The used set guarantees that no digit repeats, and the permutation counting ensures every remaining valid suffix is included.
Since every unique-digit number <= n is counted exactly once, subtracting from n produces the exact number of integers containing repeated digits.
Python Solution
class Solution:
def numDupDigitsAtMostN(self, n: int) -> int:
digits = list(map(int, str(n + 1)))
length = len(digits)
def permutation(m: int, k: int) -> int:
result = 1
for i in range(k):
result *= (m - i)
return result
unique_count = 0
# Count numbers with fewer digits
for digits_count in range(1, length):
unique_count += 9 * permutation(9, digits_count - 1)
used = set()
# Count numbers with same length
for i in range(length):
current_digit = digits[i]
for digit in range(0 if i > 0 else 1, current_digit):
if digit in used:
continue
remaining_positions = length - i - 1
available_digits = 10 - (i + 1)
unique_count += permutation(
available_digits,
remaining_positions
)
if current_digit in used:
break
used.add(current_digit)
return n - unique_count
The implementation begins by converting n + 1 into a digit array. This allows the algorithm to count all unique-digit numbers strictly smaller than n + 1, which corresponds exactly to numbers less than or equal to n.
The permutation helper computes:
P(m, k) = m × (m - 1) × ...
This is used repeatedly when determining how many valid suffixes can be formed.
The first loop counts all unique-digit numbers with fewer digits than n.
The second loop processes numbers with the same length digit by digit. At each position, it tries every smaller valid digit and computes how many completions remain possible.
The used set ensures that no digit repeats within the current prefix.
If the current digit has already appeared, the algorithm stops immediately because every continuation would contain repeated digits.
Finally, subtracting unique_count from n yields the number of integers containing repeated digits.
Go Solution
func numDupDigitsAtMostN(n int) int {
digits := []int{}
temp := n + 1
for temp > 0 {
digits = append([]int{temp % 10}, digits...)
temp /= 10
}
length := len(digits)
permutation := func(m, k int) int {
result := 1
for i := 0; i < k; i++ {
result *= (m - i)
}
return result
}
uniqueCount := 0
// Count numbers with fewer digits
for digitsCount := 1; digitsCount < length; digitsCount++ {
uniqueCount += 9 * permutation(9, digitsCount-1)
}
used := make(map[int]bool)
// Count numbers with same length
for i := 0; i < length; i++ {
currentDigit := digits[i]
start := 0
if i == 0 {
start = 1
}
for digit := start; digit < currentDigit; digit++ {
if used[digit] {
continue
}
remainingPositions := length - i - 1
availableDigits := 10 - (i + 1)
uniqueCount += permutation(
availableDigits,
remainingPositions,
)
}
if used[currentDigit] {
break
}
used[currentDigit] = true
}
return n - uniqueCount
}
The Go implementation follows the same logic as the Python version.
One notable difference is that Go does not provide a built-in set type, so a map[int]bool is used to track used digits.
Another difference is digit extraction. Since Go lacks Python's convenient string-to-digit conversion style, digits are extracted manually using modulo and division operations.
Integer overflow is not a concern because the problem constraints are limited to 10^9, and all intermediate permutation values remain well within Go's integer range.
Worked Examples
Example 1
Input:
n = 20
We process 21.
Count numbers with fewer digits
| Digits | Count |
|---|---|
| 1-digit unique numbers | 9 |
Current total:
unique_count = 9
Process 2-digit numbers
Digits of 21:
[2, 1]
| Position | Current Digit | Used | Smaller Valid Digits | Added Count |
|---|---|---|---|---|
| 0 | 2 | {} | 1 | 9 |
| 1 | 1 | {2} | 0 | 1 |
Final:
unique_count = 19
Result:
20 - 19 = 1
Answer:
1
Example 2
Input:
n = 100
We process 101.
Count shorter lengths
| Digits | Count |
|---|---|
| 1-digit | 9 |
| 2-digit | 81 |
Total:
90
Process 3-digit numbers
Digits:
[1, 0, 1]
| Position | Digit | Used | Added |
|---|---|---|---|
| 0 | 1 | {} | 0 |
| 1 | 0 | {1} | 0 |
| 2 | 1 | {1,0} | repetition found |
Final:
unique_count = 90
Result:
100 - 90 = 10
Example 3
Input:
n = 1000
We process 1001.
Count shorter lengths
| Digits | Count |
|---|---|
| 1-digit | 9 |
| 2-digit | 81 |
| 3-digit | 648 |
Total:
738
During same-length processing, repetition appears early because of repeated zeros.
Final:
1000 - 738 = 262
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O((log n)^2) | Digit count is at most 10, and each position performs bounded permutation calculations |
| Space | O(log n) | Used set and digit storage scale with number of digits |
The algorithm is extremely efficient because the number of digits in n is small. Even for the maximum input 10^9, there are only 10 digits to process. The nested loops therefore remain tiny in practice.
Test Cases
solution = Solution()
assert solution.numDupDigitsAtMostN(1) == 0 # single digit
assert solution.numDupDigitsAtMostN(9) == 0 # all unique single digits
assert solution.numDupDigitsAtMostN(10) == 0 # includes zero but no repetition
assert solution.numDupDigitsAtMostN(11) == 1 # first repeated-digit number
assert solution.numDupDigitsAtMostN(20) == 1 # provided example
assert solution.numDupDigitsAtMostN(99) == 9 # repeated doubles only
assert solution.numDupDigitsAtMostN(100) == 10 # provided example
assert solution.numDupDigitsAtMostN(101) == 11 # 100 and 101 both repeat
assert solution.numDupDigitsAtMostN(110) == 12 # multiple repeated values
assert solution.numDupDigitsAtMostN(1000) == 262 # provided example
assert solution.numDupDigitsAtMostN(999) == 261 # all 3-digit repeated combinations
assert solution.numDupDigitsAtMostN(1023) == 285 # mixed prefix handling
assert solution.numDupDigitsAtMostN(5000) > 0 # larger range stress case
assert solution.numDupDigitsAtMostN(10**9) > 0 # maximum constraint
| Test | Why |
|---|---|
n = 1 |
Smallest valid input |
n = 9 |
No repeated digits possible |
n = 10 |
Ensures zero handling works |
n = 11 |
First repeated-digit number |
n = 20 |
Verifies sample case |
n = 99 |
All repeated double-digit values |
n = 100 |
Tests repeated zeros |
n = 101 |
Repetition separated by another digit |
n = 110 |
Multiple repeated digits |
n = 1000 |
Larger repeated-zero scenario |
n = 999 |
Dense repetition range |
n = 1023 |
Complex prefix counting |
n = 5000 |
Medium-scale stress test |
n = 10^9 |
Maximum constraint |
Edge Cases
One important edge case is very small values such as n = 1 or n = 9. These numbers contain only one digit, so repetition is impossible. A buggy implementation might accidentally count leading zeros or mishandle empty permutations. This implementation correctly returns 0 because the unique-digit count equals n.
Another critical edge case involves repeated zeros, such as 100, 1000, or 10000. These are tricky because the repetition does not occur among nonzero digits. The algorithm handles this correctly by tracking every used digit, including zero, in the used set.
A third important edge case occurs when repetition appears late in the number, such as 123451. The prefix 12345 is valid, but the final digit repeats 1. The algorithm detects this immediately during left-to-right processing and stops further counting because every continuation from that prefix necessarily contains repeated digits.
A fourth subtle case is numbers near powers of ten, such as 99, 100, 999, and 1000. These boundaries often cause off-by-one errors in digit DP solutions. Using n + 1 instead of n simplifies inclusive counting and avoids these boundary mistakes cleanly.