Đếm số có chữ số duy nhất trong C++

Mô tả bài toán

Cho n không âm. Đếm số nguyên x trong [0, 10^n) có tất cả chữ số khác nhau.

Ví dụ: n=2 → 91 (từ 0 đến 99 trừ 9 số 11,22,...,99).

Giải thuật Toán học tổ hợp

• n=0: 1 số (0).
• n=1: 10 số (0-9).
• : số k chữ số (k≥2, không dẫn 0) = 9 * 9 * 8 * ... * (11-k).
  • Chữ số đầu: 9 lựa chọn (1-9).
  • Chữ số 2: 9 lựa chọn (0-9 trừ chữ số đầu).
  • Chữ số 3: 8 lựa chọn...
• Tổng = 10 + Σ_{k=2..min(n,10)} (9 * P(9, k-1)).
• n > 10 → kết quả giống n=10 (chỉ có 10 chữ số).

Cài đặt C++

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

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

int main() {
    Solution ob;
    cout << ob.countNumbersWithUniqueDigits(3); // 739
    return 0;
}

Độ phức tạp

• Thời gian: O(min(n,10)) = O(1).
• Không gian: O(1).