Count Numbers With Unique Digits Problem

1
2
3
Input: n = 2
Output: 91
Explanation: The answer should be the total numbers in the range of 0 &le; x < 100, excluding 11,22,33,44,55,66,77,88,99

1
2
Input: n = 0
Output: 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
For n = 0, ans = 1
For n = 1, ans = 10
If we take 2 digit number, we have 9 options for first digit (1 - 9)
and 9 options for second digit(0 & all other digits except the one taken as first digit (to keep digits unique)) therefore ans += (9 * 9)
Similarly if we take 3 digit number we have 8 options for third digit, therefore ans += (9 * 9 * 8)
*/
class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        if(n == 0)
            return 1;
        int ans = 10, calc = 9, temp = 9;
        for(int i = 0; i < n - 1; i++) {
            calc *= temp;
            ans += calc;
            temp--;
        }
        return ans;
    }
};