How to Count Numbers with Unique Digits?

Given a non-negative integer n, please find out the number of integers that have the unique digits between [0, 10^n). For example, if n = 2, there are 91 numbers between 0 (inclusive) to 100 (exclusive) that have the unique digits (excluding 11, 22, 33, 44, 55, 66 ,77, 88 and 99).

Combinatorics

First, it is easy to find out that there are no numbers that have unique digits if length is larger than 10 because there will be at least 1 duplicate digit to use 10 digits in a number that has length larger than 10 (pigeon-hole principle). So the answer would be:

where f(i) denotes the number with unique digits for length i.

For numbers between [10, 99], the answer is 9*9=81 because number cannot start with zero.
For numbers between [100, 999], the answer is 9*9*8 ..

So a straightforward C++ implementation is to add these:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        if (n == 0) return 1;
        int sum = 10;
        for (int i = 2; i <= min(n, 10); i ++) {
            int nn = 9;
            for (int j = 9; j >= 9 - i + 2; j --) {
                nn *= j;
            }
            sum += nn;
        }
        return sum;
    }
};

class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        if (n == 0) return 1;
        int sum = 10;
        for (int i = 2; i <= min(n, 10); i ++) {
            int nn = 9;
            for (int j = 9; j >= 9 - i + 2; j --) {
                nn *= j;
            }
            sum += nn;
        }
        return sum;
    }
};

This puzzle can also be solved using backtracking but it is not efficient/intuitive as this Dynamic Programming approach.

See also: Teaching Kids Programming – Dynamic Programming Algorithms to Count Numbers with Unique Digits

–EOF (The Ultimate Computing & Technology Blog) —