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:

  • 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)

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;
}

Last updated