นับจำนวนที่มีตัวเลขไม่ซ้ำใน C++

ให้จำนวนเต็มไม่ติดลบ n นับจำนวน x ในช่วง [0, 10^n) ที่ตัวเลขทุกหลักไม่ซ้ำกัน

ตัวอย่าง: n=2 → 91 (0-99 ยกเว้น 11,22,33,44,55,66,77,88,99)

ขั้นตอนการแก้ปัญหา (Combinatorics)

1. ถ้า n == 0 → 1 (แค่ 0)
2. n = min(n, 10) (มากกว่า 10 หลักไม่มีตัวเลขไม่ซ้ำได้)
3. ถ้า n == 1 → 10 (0-9)
4. ans = 9 (หลักแรก 1-9), ret = 10 (รวม 0)
5. วน i = 2..n:
   • ans *= (9 - i + 2) (หลักที่ i มีตัวเลือกเหลือ 9-(i-1) = 11-i ตัว)
   • ret += ans
6. คืน ret

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        if (n == 0) return 1;
        n = min(10, n);
        if (n == 1) return 10;
        int ans = 9, ret = 10;
        for (int i = 2; i <= n; i++) {
            ans *= (9 - i + 2);
            ret += ans;
        }
        return ret;
    }
};

int main() {
    Solution ob;
    cout << ob.countNumbersWithUniqueDigits(3);
}

Input

3

Output

739