0357. Count Numbers with Unique Digits

https://leetcode.com/problems/count-numbers-with-unique-digits

Description

Given an integer n, return the count of all numbers with unique digits, x, where 0 <= x < 10n.

Example 1:

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

Example 2:

**Input:** n = 0
**Output:** 1

Constraints:

• 0 <= n <= 8

ac1: brute force

class Solution {
    int res;
    int[] used;
    public int countNumbersWithUniqueDigits(int n) {
        // edge cases
        if (n == 0) return 1;

        res = 0;
        used = new int[10];
        helper(n, 0, true);
        return res;
    }

    private void helper(int remain, int curr, boolean canRepeatZero) {
        // exit, no more digits, return
        if (remain == 0) { 
            res++;
            return;
        }

        for (int i = 0; i <= 9; i++) {
            if (used[i] > 0 && (i != 0 || !canRepeatZero)) continue;
            used[i]++;
            boolean tmp = !canRepeatZero ? false : curr == 0 || i != 0;
            helper(remain-1, curr*10+i, tmp);
            used[i]--;
        }
    }
}

ac: trick

class Solution {
    public int countNumbersWithUniqueDigits(int n) {
        if (n == 0) return 1;

        int res = 10;  // when n == 1
        int nRes = 9;
        int nextDigit = 9;
        while (n > 1 && nextDigit > 0) {
            nRes = nRes * nextDigit;
            res += nRes;
            n--;
            nextDigit--;
        }

        return res;
    }
}