Given an integer n, return the number of positive integers in the range [1, n] that have at least one repeated digit.
Example 1:
Input: n = 20 Output: 1 Explanation: The only positive number (<= 20) with at least 1 repeated digit is 11.
Example 2:
Input: n = 100 Output: 10 Explanation: The positive numbers (<= 100) with atleast 1 repeated digit are 11, 22, 33, 44, 55, 66, 77, 88, 99, and 100.
Example 3:
Input: n = 1000 Output: 262
Constraints:
1 <= n <= 109Problem Overview: Given an integer n, count how many numbers in the range [1, n] contain at least one repeated digit. Instead of directly searching for duplicates, the key trick is counting numbers with unique digits and subtracting from the total.
Approach 1: Backtracking with Digit Tracking (Exponential, O(10^d) time, O(d) space)
This approach generates numbers digit by digit using backtracking while tracking which digits are already used. A boolean array or bitmask records used digits. Start from the most significant digit and recursively append digits that haven't been used yet. Whenever the constructed number exceeds n, stop exploring that branch. Numbers that reuse a digit are counted as repeated-digit numbers.
The insight is simple: simulate the construction of numbers while enforcing uniqueness. If a digit is reused, the number contains repeated digits. While easy to reason about and good for learning, the branching factor can reach 10 per level. For numbers with d digits the worst-case time is roughly O(10^d) with recursion depth d. This approach demonstrates the mechanics behind digit construction and connects naturally to Math counting problems.
Approach 2: Dynamic Programming + Combinatorial Counting (Optimal, O(d * 2^10) time, O(2^10 * d) space)
The optimal solution flips the problem: count numbers with all unique digits and subtract from n. Convert n to a digit array and process it from left to right. At each position, try placing a smaller digit that hasn't appeared before. For every valid prefix, count how many permutations of the remaining digits exist using combinatorial math.
This is essentially a digit DP problem. The state tracks the current index, which digits are used (bitmask of size 10), and whether the prefix is already smaller than the corresponding prefix of n. Each transition chooses the next digit that isn't used yet. When the number length is smaller than n, permutations are counted directly using P(9, k)-style calculations. Because there are at most d positions and 2^10 digit masks, the complexity stays around O(d * 2^10).
This approach blends Dynamic Programming with combinatorics. It avoids enumerating actual numbers and instead counts valid configurations mathematically. The final result is n - uniqueCount, which gives the number of integers containing repeated digits.
Recommended for interviews: Interviewers typically expect the combinatorial digit-DP approach. The backtracking method shows you understand the constraint that digits cannot repeat, but the optimal counting strategy demonstrates stronger algorithmic thinking and familiarity with digit DP patterns.
The idea is to count numbers without repeated digits and subtract from the total count. By using backtracking, we can generate all numbers up to n with unique digits and calculate how many of them are there.
This Python code calculates the number of numbers <= N with no repeated digits, subtracts it from N, and returns the result. It breaks down the number N, evaluates numbers smaller than N up to the same digit count, and uses permutations to count valid numbers efficiently.
Time Complexity: O(log(N)^2) due to digit iteration.
Space Complexity: O(log(N)) due to use of list structure.
Formulate a solution using dynamic programming and combinatorial principles to count non-repeating digits and derive the count of repeating digits by subtraction. This approach systematically builds permutations of possible combinations of digits and calculates possibilities using factorial numbers.
This Java solution breaks down the input number into its digits, calculates the count of numbers without repeated digits using combinatorial counting and recursion, and subtracts that count from the total number N. Similar to the previous solutions with adaptations for Java structure and syntax.
Java
JavaScript
Time Complexity: O(log(N)^2) where log represents processing by digits.
Space Complexity: O(log(N)) for the boolean array definition.
The problem requires counting the number of integers in the range [1, .., n] that have at least one repeated digit. We can approach this by defining a function f(n) that counts the number of integers in the range [1, .., n] with no repeated digits. Then, the answer is n - f(n).
Additionally, we can use a binary number to record the digits that have appeared in the number. For example, if the digits 1, 2, and 4 have appeared, the corresponding binary number is \underline{1}0\underline{1}\underline{1}0.
Next, we use memoization to implement digit DP. We start searching from the top, get the number of solutions at the bottom, and return the answers layer by layer until we get the final answer from the starting point.
The basic steps are as follows:
We convert the number n into a string s. Next, we design a function dfs(i, mask, lead, limit), where:
i represents the current digit index, starting from 0.mask represents the digits that have appeared so far, using a binary number. The j-th bit of mask being 1 indicates that digit j has appeared, while 0 indicates it has not.lead indicates whether the current number contains only leading zeros.limit indicates whether the current position is restricted by the upper bound.The function executes as follows:
If i is greater than or equal to m, it means we have processed all digits. If lead is true, it means the current number is a leading zero, and we should return 0. Otherwise, we should return 1.
Otherwise, we calculate the upper bound up. If limit is true, then up is the digit corresponding to s[i]. Otherwise, up is 9.
Then, we enumerate the current digit j in the range [0, up]. If j is 0 and lead is true, we recursively calculate dfs(i + 1, mask, true, limit \wedge j = up). Otherwise, if the j-th bit of mask is 0, we recursively calculate dfs(i + 1, mask \,|\, 2^j, false, limit \wedge j = up). We accumulate all the results as the answer.
The answer is n - dfs(0, 0, true, true).
The time complexity is O(log n times 2^D times D), and the space complexity is O(log n times 2^D). Here, D = 10.
Similar problems:
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Backtracking Approach | Time Complexity: O(log(N)^2) due to digit iteration. |
| Dynamic Programming and Combinatorial Counting | Time Complexity: O(log(N)^2) where log represents processing by digits. |
| State Compression + Digit DP | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Digit Tracking | O(10^d) | O(d) | Useful for understanding digit construction and recursion; feasible only for small ranges. |
| Digit DP + Combinatorial Counting | O(d * 2^10) | O(d * 2^10) | Optimal for large n (up to 10^9). Counts valid digit permutations efficiently. |
Numbers With Repeated Digits | LeetCode 1012 | Coders Camp • Coders Camp • 8,086 views views
Watch 9 more video solutions →Practice Numbers With Repeated Digits with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor