357 Count Numbers with Unique Digits

Given anon-negativeinteger n, count all numbers with unique digits, x, where 0 ≤ x < 10n.

Example: Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding[11,22,33,44,55,66,77,88,99])

The Idea:

• If n == 0, we can only chose $10^0 = 1$ or just one thing.

• When n == 1, we can choose $0 \leq x < 10$ things, that is $0,1,2,3,4,5,6,7,8,9$ things

• When n == 2, we can choose a permutation of 2 things, that is...

01, 02, 03 ... 09
12, 13, 14 ... 19
21, 23, 24 ... 29

• Which equates to P(10, 2) things. But we have some redundancy, that is those 0's in the beginning, which are effectively the same thing as 0,1,2,3,4,...9. To get rid of these, we subtract P(9,1) to get rid of just those 9 elements.

• When n == 4, we can likewise chose P(10,4) things. But what is the redundancy here. Lets think about it.

012, 013, .. 019
021, 023, .. 029
031, 032, .. 039

...

091, 092, .. 098

• We find 9 elements per row, for 8 rows. This follows 9*8, or P(9,2)

• It then follows that the number of numbers of unique Digits are $\sum_{i=1}^n{P(10, i) - P(9, i - 1)}$

int permutation(int num, int choose)
{
    int cur = 1;
    int go_to = num - choose;
    for (int i = num; i > go_to; i--)
        cur *= i;

    return cur == 1 ? 0 : cur;
}

int countNumbersWithUniqueDigits(int n) 
{
    if (n == 0) return 1;
    int prev_perm = 0;
    for (int i = 1; i <= n; i++) {
        prev_perm += permutation(10, i) - permutation(9, i - 1);
    }

    return prev_perm;
}