Count Numbers with Unique Digits Solutions in C++

// Source : https://leetcode.com/problems/count-numbers-with-unique-digits/
// Author : Hao Chen
// Date   : 2019-03-24




// Considering three digits
//   - the first place could be [1-9] which has 9 choices.
//   - the second place could be [0-9] with excluding the first digit, which is 10-1=9 choices.
//   - the third place could be [0-9] with excluding the 1st and 2nd digits, which is 10-2=8 choices.
// So, three digits has 9*9*8 unique digits.
//
// After adds the 1 digit unique number,and 2 digits unique number, we can have the result:
//
//   9*9*8 + 9*9 + 10 = 648 + 81 + 10 = 739
//
// n = 0, a[0] = 1;
// n = 1, a[1] = 9 + a[0];
// n = 2, a[2] = 9*9 + a[1];
// n = 3, a[3] = 9*9*8 + a[2];
// n = 4, a[4] = 9*9*8*7 + a[3];
// ....
class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        int result = 1;
        for (int i=0; i<n; i++) {
            result += ( 9 * nine_factor(i) );
        }
        return result;
    }

    int nine_factor(int n) {
        int result = 1;
        for (int i=0; i<n; i++) {
            result *= (9-i);
        }
        return result;
    }
};


//actually, the function nine_factor() could be optimized!

class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        int result = 1;
        int nine_factor = 1;
        for (int i=0; i<n; i++) {
            result += ( 9 * nine_factor );
            nine_factor *= (9-i);
        }
        return result;
    }


};