LeetCode 357

Description

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

###Thinking: This is a permuation problem. The challenge is to deal with the situation when the highest digit is zero. Based on whether the highest digit is zero or none-zero, we can use DP to solve the problem. Define function f(n) as the current solution when n. There are two situations:

  1. When the highest digit is zero, the solution is f(n-1).
  2. When the highest digit is none-zero, the solution is $9\times9\times8\times…\times(11-n)$ ; Add up to two siuations, f(n) = f(n-1) + $9\times9\times8\times…\times(11-n)$

when n=0, f(0) = 1; when n=1, besides 0(f(0)), there are 9 numbers with unique digits, namely, f(1) = f(0) + 9 = 10; when n=2, there are two situations: 1. When the highest digit is zero, there are f(1) numbers with unique digits; 2. when the highest digit is none-zero, the highest digit has 9 choices(1,2,…9, excluding 0), correspondingly the lowerest digit has 9 choices(including 0)for unique digit. Namely, f(2) = f(1) + $9\times9$ = 91; when n=3, there are two situtaions: 1. When the highest is zero, there are f(2) numbers with unique digits; 2.when the highest is none-zero, the highest digit has 9 choices, the 2th digit has 9 choices, the 3th digit has 8 choices. Namely, f(3) = f(2) + $9\times9\times8$ = 739; … f(n) = f(n-1) + $9\times9\times8\times…\times(11-n)$

Note: when n = 10： f(10) = f(9) + $9\times9\times8\times…\times1$ When n >= 11: For 11-digit or more than 11 digits numbers, there is no numbers with unique digits.Thus, return f(10).

###Solution:

public int countNumbersWithUniqueDigits(int n) {
    int[] dp = new int[n+1];
    dp[0] = 1;
    for(int i=1;i<=n;i++){
        if(i>10){
            return dp[10];
        }
        int s = 9;
        for(int j=i;j>1;j--)
            s*=(11-j);
        dp[i]=dp[i-1]+s;
    }
    return dp[n];
}