Count Numbers with Unique Digits

Problem

Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10^n.

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

Solution

O(1) Counting Solution

public class Solution {
    public int countNumbersWithUniqueDigits(int n) {
        if (n <= 0) return 1;
        int res = 10, count = 9, digits = 9;
        while (n-- > 1 && digits > 0) {
            count *= digits--; 
            res += count;
        }
        return res;
    }
}

Analysis

For any n <= 0 the only number with unique digit is 0
Then starting from n = 1 we have 10 numbers qualified
We get the total numbers by doing a simple counting algorithm
When n = 2, we can pick 9 numbers and combine them with other 9 numbers (0 cannot be combined)
Then we have 8 numbers left to use
Continue the loop until there is no more available digits or n <= 1
That means the loop will run for 9 times at most, hence, it's O(1) time