Count Numbers with Unique Digits

medium math combinatorics

Problem

Count all numbers in [0, 10^n) whose digits are all distinct.

Inputn = 2

Output91

100 total values minus 9 two-digit numbers with repeats (11, 22, …, 99).

n (0..10)

def count_numbers_with_unique_digits(n):
    if n == 0:
        return 1
    total = 10
    block = 9
    avail = 9
    for _ in range(2, n + 1):
        block *= avail
        total += block
        avail -= 1
    return total

function countNumbersWithUniqueDigits(n) {
  if (n === 0) return 1;
  let total = 10, block = 9, avail = 9;
  for (let k = 2; k <= n; k++) {
    block *= avail;
    total += block;
    avail--;
  }
  return total;
}

class Solution {
    public int countNumbersWithUniqueDigits(int n) {
        if (n == 0) return 1;
        int total = 10, block = 9, avail = 9;
        for (int k = 2; k <= n; k++) {
            block *= avail;
            total += block;
            avail--;
        }
        return total;
    }
}

int countNumbersWithUniqueDigits(int n) {
    if (n == 0) return 1;
    int total = 10, block = 9, avail = 9;
    for (int k = 2; k <= n; k++) {
        block *= avail;
        total += block;
        avail--;
    }
    return total;
}

Explanation

Instead of listing every number below 10^n and checking it, we just count the choices for each digit position. This turns the whole problem into a tiny multiplication.

Think of building a number with a fixed length. The first digit can be anything from 1 to 9 (no leading zero), so it has 9 choices. The second digit can be any of 0-9 except the one already used, so 9 choices again. The third has 8 left, the fourth 7, and so on — each new digit has one fewer option because digits cannot repeat.

The code adds up these counts one length at a time. It starts total = 10 for the single-digit numbers (0-9), keeps a running block = 9, and each loop multiplies block by avail (the remaining choices) and adds it to total, then shrinks avail by one.

Example with n = 2: one-digit gives 10. Two-digit gives 9 × 9 = 81 (first digit 9 options, second digit 9 options). Total is 10 + 81 = 91, which matches the expected answer.

Because we only loop up to n and do a couple of multiplications each time, this is very fast and uses almost no memory.

Time: O(n) Space: O(1)