Count Special Integers

Hard
1054.

Count Special Integers

Count Special Integers is a hard coding problem on dynamic programming, math and combinatorics, asked in Amazon, Google and Microsoft interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var countSpecialNumbers = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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

  1. Hint 1

    Split the count by number of digits. Anything shorter than n is unconstrained: the first digit has 9 choices and each later digit one fewer than the last.

  2. Hint 2

    For numbers with the same digit count as n, fix a common prefix and let the next digit be strictly smaller than n's.

  3. Hint 3

    Stop the prefix walk the moment n itself 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

  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

Java

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