Numbers With Repeated Digits solution and explanation
Google
9 more videos on this problem
Numbers With Repeated Digits | LeetCode 1012 | Coders CampCoders Camp · 19:32 · 8K views
L-03. (Digit + Bitmask) DP | Numbers with Repeated Digits | Leetcode 1012 | Recursive + MemoizationWhy Not DP [By Piyush Raj] · 50:34 · 3K views
1012. Numbers With Repeated Digits (Leetcode Hard)Programming Live with Larry · 25:55 · 1K views
【每日一题】LeetCode 2376. Count Special Integers (aka. LC 1012.Numbers With Repeated Digits)Huifeng Guan · 27:09 · 1K views
猩猩的乐园 Leetcode 1012 Numbers With Repeated Digits猩猩的乐园 · 11:49 · 576 views
Digit Dp | 1012. Numbers With Repeated Digits | Patterns | C++ Code | Dynamic ProgrammingJayash Todi · 15:25 · 531 views
Leetcode 1012. Numbers With Repeated DigitsFearless Learner · 11:02 · 502 views
leetcode 1012 Numbers With Repeated DigitsCoder on A Farm · 12:21 · 330 views
猩猩的乐园 Leetcode 1012 Numbers With Repeated Digits猩猩的乐园 · 10:50 · 220 views
No Sound Leetcode 1012: Numbers with Repeated DigitsExtremeProgrammer · 5:50 · 18 views
The problem
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 <= 109
Approach overview
Problem 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.
Approach 1: Backtracking Approach
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.
def numDupDigitsAtMostN(N):
L = list(map(int, str(N + 1)))
n = len(L)
res = sum(9 * perm(9, i) for i in range(n - 1))
used = set()
for i, x in enumerate(L):
for y in range(i == 0, x):
if y in used: continue
res += perm(9 - i, n - i - 1)
if x in used: break
used.add(x)
return N - res
def perm(m, n):
return 1 if n == 0 else perm(m, n - 1) * (m - n + 1)#include <vector>
#include <string>
using namespace std;
class Solution {
public:
int numDupDigitsAtMostN(int N) {
vector<int> L;
for (int x = N + 1; x > 0; x /= 10)
L.insert(L.begin(), x % 10);
int n = L.size(), res = 0;
for (int i = 0; i < n - 1; ++i)
res += 9 * A(9, i);
vector<bool> used(10, false);
for (int i = 0; i < n; ++i) {
for (int x = (i == 0 ? 1 : 0); x < L[i]; ++x) {
if (!used[x])
res += A(9 - i, n - i - 1);
}
if (used[L[i]]) break;
used[L[i]] = true;
}
return N - res;
}
private:
int A(int m, int n) {
return n == 0 ? 1 : A(m, n - 1) * (m - n + 1);
}
};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.
Approach 2: Dynamic Programming and Combinatorial Counting
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.
class Solution {
public int numDupDigitsAtMostN(int N) {
String S = Integer.toString(N + 1);
int n = S.length();
int res = 0;
for (int i = 1; i < n; ++i)
res += 9 * A(9, i - 1);
boolean[] used = new boolean[10];
for (int i = 0; i < n; ++i) {
for (int x = (i == 0 ? 1 : 0); x < S.charAt(i) - '0'; ++x) {
if (!used[x])
res += A(9 - i, n - i - 1);
}
if (used[S.charAt(i) - '0']) break;
used[S.charAt(i) - '0'] = true;
}
return N - res;
}
private int A(int m, int n) {
return n == 0 ? 1 : A(m, n - 1) * (m - n + 1);
}
}function numDupDigitsAtMostN(N) {
let L = [];
for (let x = N + 1; x > 0; x = Math.floor(x / 10))
L.unshift(x % 10);
const A = (m, n) => n === 0 ? 1 : A(m, n - 1) * (m - n + 1);
let res = 0, n = L.length;
for (let i = 1; i < n; ++i)
res += 9 * A(9, i - 1);
let used = new Array(10).fill(false);
for (let i = 0; i < n; ++i) {
for (let x = (i == 0 ? 1 : 0); x < L[i]; ++x) {
if (!used[x])
res += A(9 - i, n - i - 1);
}
if (used[L[i]]) break;
used[L[i]] = true;
}
return N - res;
}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.
Time Complexity: O(log(N)^2) where log represents processing by digits.
Space Complexity: O(log(N)) for the boolean array definition.
Approach 3: State Compression + Digit DP
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:
- The integer
irepresents the current digit index, starting from0. - The integer
maskrepresents the digits that have appeared so far, using a binary number. Thej-th bit ofmaskbeing1indicates that digitjhas appeared, while0indicates it has not. - The boolean
leadindicates whether the current number contains only leading zeros. - The boolean
limitindicates 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:
function numDupDigitsAtMostN(n: number): number {
const s = n.toString();
const m = s.length;
const f = Array.from({ length: m }, () => Array(1 << 10).fill(-1));
const dfs = (i: number, mask: number, lead: boolean, limit: boolean): number => {
if (i >= m) {
return lead ? 0 : 1;
}
if (!lead && !limit && f[i][mask] !== -1) {
return f[i][mask];
}
const up = limit ? parseInt(s[i]) : 9;
let ans = 0;
for (let j = 0; j <= up; j++) {
if (lead && j === 0) {
ans += dfs(i + 1, mask, true, limit && j === up);
} else if (((mask >> j) & 1) === 0) {
ans += dfs(i + 1, mask | (1 << j), false, limit && j === up);
}
}
if (!lead && !limit) {
f[i][mask] = ans;
}
return ans;
};
return n - dfs(0, 0, true, true);
}func numDupDigitsAtMostN(n int) int {
s := []byte(strconv.Itoa(n))
m := len(s)
f := make([][]int, m)
for i := range f {
f[i] = make([]int, 1<<10)
for j := range f[i] {
f[i][j] = -1
}
}
var dfs func(i, mask int, lead, limit bool) int
dfs = func(i, mask int, lead, limit bool) int {
if i >= m {
if lead {
return 0
}
return 1
}
if !lead && !limit && f[i][mask] != -1 {
return f[i][mask]
}
up := 9
if limit {
up = int(s[i] - '0')
}
ans := 0
for j := 0; j <= up; j++ {
if lead && j == 0 {
ans += dfs(i+1, mask, true, limit && j == up)
} else if mask>>j&1 == 0 {
ans += dfs(i+1, mask|(1<<j), false, limit && j == up)
}
}
if !lead && !limit {
f[i][mask] = ans
}
return ans
}
return n - dfs(0, 0, true, true)
}Complexity comparison
| 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 | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Numbers With Repeated Digits easy or hard?
Numbers With Repeated Digits is classified as Hard on LeetCode because it requires recognizing a digit DP pattern and combining it with permutation counting. Developers unfamiliar with digit DP often find the transition logic and state representation challenging.
Numbers With Repeated Digits Python/Java solution
Python and C++ implementations often demonstrate the backtracking approach for clarity, while Java and JavaScript versions typically implement digit DP with combinatorial counting. All versions rely on tracking used digits and counting valid permutations efficiently.
How to solve Numbers With Repeated Digits in O(n)?
The problem is not solved in linear O(n) time relative to the value of n. Instead, it is solved relative to the number of digits. The digit DP approach processes each digit position and tracks used digits with a bitmask, resulting in O(d * 2^10) complexity where d is the digit count.
What is the best approach for Numbers With Repeated Digits?
The optimal approach uses digit dynamic programming with combinatorial counting. Instead of directly counting numbers with repeated digits, count numbers with unique digits up to n and subtract from n. The algorithm tracks used digits with a bitmask and evaluates digit choices position by position. Time complexity is roughly O(d * 2^10), where d is the number of digits in n.
Is Numbers With Repeated Digits asked at Google/Amazon/Meta?
Digit DP and combinatorial counting problems like Numbers With Repeated Digits appear in interviews at companies such as Google, Amazon, and Meta. The question tests understanding of permutations, digit constraints, and dynamic programming on numeric representations.
What data structure is used in Numbers With Repeated Digits?
The solution commonly uses a bitmask to represent which digits (0–9) have already appeared in the current number. This compact structure enables efficient state transitions in digit DP. Some implementations also use recursion with memoization tables for DP states.
What is the time complexity of Numbers With Repeated Digits?
The optimal digit DP solution runs in O(d * 2^10) time and O(d * 2^10) space, where d is the number of digits in n (at most 10 for typical constraints). A naive backtracking approach can reach O(10^d) time because it explores many digit combinations recursively.