Numbers With Repeated Digits
HardUpdated: Aug 2, 2025
Practice on:
Problem
Given an integer n, return the number of positive integers in the range [1, n] that have at least one repeated digit.
Examples
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
Solution
Method 1 – Digit DP (Count Unique Digits, Subtract)
Intuition
Count numbers with all unique digits up to n using digit DP, then subtract from n to get numbers with repeated digits.
Approach
- Convert n to a string for digit-wise processing.
- For numbers with fewer digits than n, count all unique-digit numbers using permutations.
- For numbers with the same number of digits as n, use digit DP:
- Track used digits with a bitmask.
- For each position, try all possible digits, ensuring no repeats and not exceeding n.
- Subtract the count of unique-digit numbers from n to get the answer.
Code
C++
class Solution {
public:
int numDupDigitsAtMostN(int n) {
vector<int> digits;
int x = n;
while (x) {
digits.push_back(x % 10);
x /= 10;
}
reverse(digits.begin(), digits.end());
int k = digits.size(), ans = 0;
// Count unique-digit numbers with length < k
for (int i = 1; i < k; ++i) {
int cnt = 9;
for (int j = 1; j < i; ++j) cnt *= (10-j);
ans += cnt;
}
// Count unique-digit numbers with length == k
function<int(int, int, bool, bool)> dfs = [&](int pos, int mask, bool tight, bool leading) -> int {
if (pos == k) return leading ? 1 : 0;
int res = 0;
int up = tight ? digits[pos] : 9;
for (int d = 0; d <= up; ++d) {
if (leading && d == 0) {
res += dfs(pos+1, mask, tight && d==up, true);
} else if (!(mask & (1<<d))) {
res += dfs(pos+1, mask | (1<<d), tight && d==up, false);
}
}
return res;
};
ans += dfs(0, 0, true, true);
return n - ans + 1;
}
};
Go
func numDupDigitsAtMostN(n int) int {
digits := []int{}
x := n
for x > 0 {
digits = append([]int{x%10}, digits...)
x /= 10
}
k, ans := len(digits), 0
cnt := 1
for i := 1; i < k; i++ {
cnt = 9
for j := 1; j < i; j++ {
cnt *= (10-j)
}
ans += cnt
}
var dfs func(pos, mask int, tight, leading bool) int
dfs = func(pos, mask int, tight, leading bool) int {
if pos == k {
if leading {
return 1
}
return 0
}
res := 0
up := 9
if tight {
up = digits[pos]
}
for d := 0; d <= up; d++ {
if leading && d == 0 {
res += dfs(pos+1, mask, tight && d==up, true)
} else if mask&(1<<d) == 0 {
res += dfs(pos+1, mask|(1<<d), tight && d==up, false)
}
}
return res
}
ans += dfs(0, 0, true, true)
return n - ans + 1
}
Java
class Solution {
public int numDupDigitsAtMostN(int n) {
List<Integer> digits = new ArrayList<>();
int x = n;
while (x > 0) {
digits.add(0, x % 10);
x /= 10;
}
int k = digits.size(), ans = 0;
for (int i = 1; i < k; ++i) {
int cnt = 9;
for (int j = 1; j < i; ++j) cnt *= (10-j);
ans += cnt;
}
// DP
ans += dfs(0, 0, true, true, digits);
return n - ans + 1;
}
private int dfs(int pos, int mask, boolean tight, boolean leading, List<Integer> digits) {
if (pos == digits.size()) return leading ? 1 : 0;
int res = 0, up = tight ? digits.get(pos) : 9;
for (int d = 0; d <= up; ++d) {
if (leading && d == 0) {
res += dfs(pos+1, mask, tight && d==up, true, digits);
} else if ((mask & (1<<d)) == 0) {
res += dfs(pos+1, mask | (1<<d), tight && d==up, false, digits);
}
}
return res;
}
}
Kotlin
class Solution {
fun numDupDigitsAtMostN(n: Int): Int {
val digits = mutableListOf<Int>()
var x = n
while (x > 0) {
digits.add(0, x % 10)
x /= 10
}
val k = digits.size
var ans = 0
for (i in 1 until k) {
var cnt = 9
for (j in 1 until i) cnt *= (10-j)
ans += cnt
}
fun dfs(pos: Int, mask: Int, tight: Boolean, leading: Boolean): Int {
if (pos == k) return if (leading) 1 else 0
var res = 0
val up = if (tight) digits[pos] else 9
for (d in 0..up) {
if (leading && d == 0) {
res += dfs(pos+1, mask, tight && d==up, true)
} else if (mask and (1 shl d) == 0) {
res += dfs(pos+1, mask or (1 shl d), tight && d==up, false)
}
}
return res
}
ans += dfs(0, 0, true, true)
return n - ans + 1
}
}
Python
class Solution:
def numDupDigitsAtMostN(self, n: int) -> int:
digits = list(map(int, str(n)))
k, ans = len(digits), 0
for i in range(1, k):
cnt = 9
for j in range(1, i):
cnt *= (10-j)
ans += cnt
def dfs(pos: int, mask: int, tight: bool, leading: bool) -> int:
if pos == k:
return 1 if leading else 0
res = 0
up = digits[pos] if tight else 9
for d in range(0, up+1):
if leading and d == 0:
res += dfs(pos+1, mask, tight and d==up, True)
elif not (mask & (1<<d)):
res += dfs(pos+1, mask | (1<<d), tight and d==up, False)
return res
ans += dfs(0, 0, True, True)
return n - ans + 1
Rust
impl Solution {
pub fn num_dup_digits_at_most_n(n: i32) -> i32 {
let mut digits = vec![];
let mut x = n;
while x > 0 {
digits.insert(0, x % 10);
x /= 10;
}
let k = digits.len();
let mut ans = 0;
for i in 1..k {
let mut cnt = 9;
for j in 1..i {
cnt *= 10-j;
}
ans += cnt;
}
fn dfs(pos: usize, mask: i32, tight: bool, leading: bool, digits: &Vec<i32>) -> i32 {
if pos == digits.len() {
return if leading { 1 } else { 0 };
}
let mut res = 0;
let up = if tight { digits[pos] } else { 9 };
for d in 0..=up {
if leading && d == 0 {
res += dfs(pos+1, mask, tight && d==up, true, digits);
} else if mask & (1<<d) == 0 {
res += dfs(pos+1, mask | (1<<d), tight && d==up, false, digits);
}
}
res
}
ans += dfs(0, 0, true, true, &digits);
n - ans + 1
}
}
TypeScript
class Solution {
numDupDigitsAtMostN(n: number): number {
const digits = Array.from(String(n), Number)
const k = digits.length
let ans = 0
for (let i = 1; i < k; ++i) {
let cnt = 9
for (let j = 1; j < i; ++j) cnt *= (10-j)
ans += cnt
}
function dfs(pos: number, mask: number, tight: boolean, leading: boolean): number {
if (pos === k) return leading ? 1 : 0
let res = 0
const up = tight ? digits[pos] : 9
for (let d = 0; d <= up; ++d) {
if (leading && d === 0) {
res += dfs(pos+1, mask, tight && d===up, true)
} else if ((mask & (1<<d)) === 0) {
res += dfs(pos+1, mask | (1<<d), tight && d===up, false)
}
}
return res
}
ans += dfs(0, 0, true, true)
return n - ans + 1
}
}
Complexity
- ⏰ Time complexity:
O(k * 2^10)— k is the number of digits in n, 2^10 for bitmask. - 🧺 Space complexity:
O(k * 2^10)— For recursion stack and bitmask DP.