357. Count Numbers with Unique Digits

This is a combinatorial problem. Once you placed a number, this number can’t be placed in following positions. So for next position the total number that can be placed is one less than the current position. A trick here is for the first position, there is 9 numbers that can be placed because 0 cannot be placed in the first position, and then in second position there is still 9 numbers available including 0. Also, a special case is n is 0 where there 0<=x.

1:  class Solution {  
2:  public:  
3:    int countNumbersWithUniqueDigits(int n) {  
4:      if (n == 0) return 1;  
5:      if (n == 1) return 10;  
6:      int count = 10;  
7:      for (int i = 2; i <= n; i++) {  
8:        int tmp = 9;  
9:        for (int j = 1, k = 9; j < i && k >= 0; j++, k--) {  
10:          tmp *= k;  
11:        }  
12:        count += tmp;  
13:      }  
14:      return count;  
15:    }  
16:  };