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

Credits:
Special thanks to@memorylessfor adding this problem and creating all test cases.

Analysis:

f(k) represent how many unique numbers for numbers with k digits.

f(k) = 9 * 9 * 8 * 7 * ... * (9-k+2). basically at each spot, pick a number, next spot, one less number to pick type of combination.

Complexity:

Time: O(N)

Space: O(1)

Code:

public class Solution {
    public int countNumbersWithUniqueDigits(int n) {
        if(n == 0){
            return 1;
        }
        int total = 10;
        for(int i = 2; i <= n; i++){
            int temp = 9;
            for(int j = 9; j>=9-i+2; j--){
                temp *= j;
            }
            total +=temp;
        }
        return total;

    }
}