Numbers With Repeated Digits — Problem & Solution
Numbers With Repeated Digits solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Numbers With Repeated Digits is a hard coding problem on dynamic programming, math and combinatorics, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Dynamic Programming, Math, Combinatorics, Digit DP
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an integer n, return how many integers in the range [1, n] have at least one repeated digit — some digit appearing two or more times in their decimal form.
Example 1
Input: n = 20
Output: 1
Explanation: Only 11.
Example 2
Input: n = 100
Output: 10
Explanation: 11, 22, 33, 44, 55, 66, 77, 88, 99 and 100.
Example 3
Input: n = 1000
Output: 262
Constraints
1 <= n <= 10^9
Hints for Numbers With Repeated Digits
Hint 1
Count the complement: numbers in
[1, n]whose digits are all different, then subtract fromn.Hint 2
Numbers with fewer digits than
nare easy: withLdigits there are9 * 9 * 8 * …of them (the first digit cannot be 0).Hint 3
For numbers with as many digits as
n, walk alongn's digits: at positioni, count unused digits smaller thann[i](no leading zero), each followed by any arrangement of the remaining unused digits. Stop ifn[i]was already used.
How to solve Numbers With Repeated Digits
Count the numbers ≤ n with all-distinct digits by permutation counting along the digits of n (a digit DP done in closed form), and subtract from n.
Approach
- Work with
n + 1and count distinct-digit numbers strictly below it; let its digits beswith lengthL. - Add numbers with fewer digits: for each length
len < L,9 · P(9, len − 1), whereP(a, b) = a!/(a−b)!. - Walk
sfrom the left with a set of used digits. At positioni, for each digitx < s[i](from 1 at the first position, from 0 later) that is not used, addP(9 − i, L − i − 1)— the ways to fill the rest with distinct unused digits. - If
s[i]is already used, stop; otherwise mark it used and continue. - Return
n − count.
Why it works
Each number below n + 1 with the same length agrees with it on a prefix and then has a smaller digit at the first difference; grouping by that position and digit counts each exactly once. After fixing i + 1 distinct digits, the remaining L − i − 1 positions take distinct digits from the 10 − (i + 1) = 9 − i unused ones, in P(9 − i, L − i − 1) ways. Once the prefix of s itself repeats a digit, every longer extension of it repeats too, so the walk can stop. Using n + 1 makes the 'strictly below' count include n itself.
Complexity
- Time —
O(L · 10) with L ≤ 10 - Space —
O(1)
Pitfalls
- Leading zeros: the first digit ranges over 1–9, later digits over 0–9.
- Forgetting to stop when a digit of
nrepeats — later positions would count numbers that share that repeated prefix. - Counting below
ninstead of up tonmissesnitself (usen + 1, or add 1 whennhas distinct digits).
Reference solution
Python
def numDupDigitsAtMostN(n: int) -> int:
def perm(m: int, r: int) -> int:
res = 1
for i in range(r):
res *= m - i
return res
digits = [int(c) for c in str(n + 1)]
length = len(digits)
unique = 0
for size in range(1, length):
unique += 9 * perm(9, size - 1)
seen = set()
for i, d in enumerate(digits):
for x in range(1 if i == 0 else 0, d):
if x not in seen:
unique += perm(9 - i, length - i - 1)
if d in seen:
break
seen.add(d)
return n - uniqueJava
static int ndPerm(int m, int r) {
int res = 1;
for (int i = 0; i < r; i++) res *= m - i;
return res;
}
public static int numDupDigitsAtMostN(int n) {
String s = String.valueOf((long) n + 1);
int length = s.length();
long unique = 0;
for (int size = 1; size < length; size++) unique += 9L * ndPerm(9, size - 1);
boolean[] seen = new boolean[10];
for (int i = 0; i < length; i++) {
int d = s.charAt(i) - '0';
for (int x = i == 0 ? 1 : 0; x < d; x++) if (!seen[x]) unique += ndPerm(9 - i, length - i - 1);
if (seen[d]) break;
seen[d] = true;
}
return (int) (n - unique);
}C++
static int ndPerm(int m, int r) {
int res = 1;
for (int i = 0; i < r; i++) res *= m - i;
return res;
}
int numDupDigitsAtMostN(int n) {
string s = to_string((long long)n + 1);
int length = s.size();
long long unique = 0;
for (int size = 1; size < length; size++) unique += 9LL * ndPerm(9, size - 1);
bool seen[10] = {false};
for (int i = 0; i < length; i++) {
int d = s[i] - '0';
for (int x = i == 0 ? 1 : 0; x < d; x++) if (!seen[x]) unique += ndPerm(9 - i, length - i - 1);
if (seen[d]) break;
seen[d] = true;
}
return (int)(n - unique);
}JavaScript
var numDupDigitsAtMostN = function(n) {
var perm = function(m, r) {
var res = 1;
for (var i = 0; i < r; i++) res *= m - i;
return res;
};
var s = String(n + 1);
var length = s.length;
var unique = 0;
for (var size = 1; size < length; size++) unique += 9 * perm(9, size - 1);
var seen = [false, false, false, false, false, false, false, false, false, false];
for (var i = 0; i < length; i++) {
var d = s.charCodeAt(i) - 48;
for (var x = i === 0 ? 1 : 0; x < d; x++) if (!seen[x]) unique += perm(9 - i, length - i - 1);
if (seen[d]) break;
seen[d] = true;
}
return n - unique;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 402 dynamic programming problems · the whole catalogue
Learn the technique: Dynamic Programming