Count Special Integers — Solution in Python, Java & C++
Count Special Integers solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Count Special Integers is a hard coding problem on dynamic programming, math and combinatorics, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Hard
- Topics: Dynamic Programming, Math, Combinatorics
- Asked at: Amazon, Google, Microsoft
- 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
A positive integer is special when all of its decimal digits are distinct.
Return how many special integers lie in the range [1, n].
Example 1
Input: n = 20
Output: 19
Explanation: Every number from 1 to 20 except 11.
Example 2
Input: n = 5
Output: 5
Explanation: All single digits are special.
Example 3
Input: n = 135
Output: 110
Constraints
1 <= n <= 2 * 10^9
Hints for Count Special Integers
Hint 1
Split the count by number of digits. Anything shorter than
nis unconstrained: the first digit has 9 choices and each later digit one fewer than the last.Hint 2
For numbers with the same digit count as
n, fix a common prefix and let the next digit be strictly smaller thann's.Hint 3
Stop the prefix walk the moment
nitself repeats a digit — no longer prefix is valid.
How to solve Count Special Integers
Count in two parts. First, all special numbers with fewer digits than n: for length len that is 9 · 9 · 8 · 7 · …, one factor per position. Second, walk n's digits left to right keeping the prefix equal to n's; at each position, count the completions where this digit is strictly smaller and unused, filling the rest with any unused digits.
Approach
- Extract
n's digits and letLbe their count. - For each
lenfrom 1 toL-1, add9 · P(9, len-1). - Walk
posfrom 0 toL-1. For each unused digitdbelowdigits[pos](and above 0 atpos = 0), add the number of ways to fill the remainingL - pos - 1positions from the10 - (pos+1)still-unused digits. - If
digits[pos]is already used, stop — no longer prefix ofnis special. - Otherwise mark it used, and if this was the last position add 1 for
nitself.
Why it works
The early stop is what most implementations get wrong. Once n's own prefix repeats a digit, every number sharing that prefix is non-special, so the walk must end — continuing would count completions that can never be valid. The falling-factorial counts come from the same place: after fixing pos+1 digits, exactly 10 - (pos+1) remain, and each further position consumes one more.
Complexity
- Time —
O(L · 10) — at most about a hundred operations - Space —
O(1)
Pitfalls
- Leading zeros are not allowed, so the first digit starts at 1.
nitself must be added only when the whole walk completes without a repeat.- Breaking out at a repeated digit is mandatory, not an optimisation.
Reference solution
Python
def countSpecialNumbers(n: int) -> int:
digits = [int(c) for c in str(n)]
L = len(digits)
answer = 0
for length in range(1, L):
cnt = 9
for i in range(length - 1):
cnt *= 9 - i
answer += cnt
used = [False] * 10
for pos in range(L):
start = 1 if pos == 0 else 0
for d in range(start, digits[pos]):
if used[d]:
continue
cnt = 1
avail = 10 - (pos + 1)
for _ in range(L - pos - 1):
cnt *= avail
avail -= 1
answer += cnt
if used[digits[pos]]:
return answer
used[digits[pos]] = True
if pos == L - 1:
answer += 1
return answerJava
public static int countSpecialNumbers(int n) {
int[] digits = new int[12];
int L = 0;
for (int v = n; v > 0; v /= 10) digits[L++] = v % 10;
for (int a = 0, b = L - 1; a < b; a++, b--) {
int t = digits[a];
digits[a] = digits[b];
digits[b] = t;
}
int answer = 0;
for (int len = 1; len < L; len++) {
int cnt = 9;
for (int i = 0; i < len - 1; i++) cnt *= 9 - i;
answer += cnt;
}
boolean[] used = new boolean[10];
for (int pos = 0; pos < L; pos++) {
int start = pos == 0 ? 1 : 0;
for (int d = start; d < digits[pos]; d++) {
if (used[d]) continue;
int ways = 1;
int avail = 10 - (pos + 1);
for (int i = 0; i < L - pos - 1; i++) {
ways *= avail;
avail--;
}
answer += ways;
}
if (used[digits[pos]]) return answer;
used[digits[pos]] = true;
if (pos == L - 1) answer++;
}
return answer;
}C++
int countSpecialNumbers(int n) {
vector<int> digits;
for (int v = n; v > 0; v /= 10) digits.push_back(v % 10);
reverse(digits.begin(), digits.end());
int L = (int) digits.size();
int answer = 0;
for (int len = 1; len < L; len++) {
int cnt = 9;
for (int i = 0; i < len - 1; i++) cnt *= 9 - i;
answer += cnt;
}
vector<bool> used(10, false);
for (int pos = 0; pos < L; pos++) {
int start = pos == 0 ? 1 : 0;
for (int d = start; d < digits[pos]; d++) {
if (used[d]) continue;
int ways = 1, avail = 10 - (pos + 1);
for (int i = 0; i < L - pos - 1; i++) {
ways *= avail;
avail--;
}
answer += ways;
}
if (used[digits[pos]]) return answer;
used[digits[pos]] = true;
if (pos == L - 1) answer++;
}
return answer;
}JavaScript
var countSpecialNumbers = function(n) {
var digits = [], v, i;
for (v = n; v > 0; v = Math.floor(v / 10)) digits.push(v % 10);
digits.reverse();
var L = digits.length, answer = 0;
for (var len = 1; len < L; len++) {
var cnt = 9;
for (i = 0; i < len - 1; i++) cnt *= 9 - i;
answer += cnt;
}
var used = [];
for (i = 0; i < 10; i++) used.push(false);
for (var pos = 0; pos < L; pos++) {
var start = pos === 0 ? 1 : 0;
for (var d = start; d < digits[pos]; d++) {
if (used[d]) continue;
var ways = 1, avail = 10 - (pos + 1);
for (i = 0; i < L - pos - 1; i++) { ways *= avail; avail--; }
answer += ways;
}
if (used[digits[pos]]) return answer;
used[digits[pos]] = true;
if (pos === L - 1) answer++;
}
return answer;
};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