Get started

Count Special Integers — Hard Problem & Solution

A positive integer is special when all of its decimal digits are distinct. Return how many special integers lie in the range [1, n].

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

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

  1. Extract n's digits and let L be their count.
  2. For each len from 1 to L-1, add 9 · P(9, len-1).
  3. Walk pos from 0 to L-1. For each unused digit d below digits[pos] (and above 0 at pos = 0), add the number of ways to fill the remaining L - pos - 1 positions from the 10 - (pos+1) still-unused digits.
  4. If digits[pos] is already used, stop — no longer prefix of n is special.
  5. Otherwise mark it used, and if this was the last position add 1 for n itself.

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.
  • n itself 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 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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 213 math problems · the whole catalogue