Số có chữ số lặp lại trong C++

Cho số nguyên dương N, tìm số lượng số nguyên dương ≤ N có ít nhất một chữ số lặp lại.

Ví dụ: N = 99 → kết quả = 9 (11, 22, ..., 99).

Giải thuật

1. Đếm số lượng số KHÔNG có chữ số lặp lại (số "độc nhất") ≤ N, sau đó trừ từ N.
2. Hàm A(m, n) tính số hoán vị: m * (m-1) * ... * (m-n+1).
3. Tách N thành mảng chữ số arr (từ cao đến thấp).
4. Đếm các số có ít chữ số hơn N: với độ dài i từ 1 đến n-1, cộng 9 * A(9, i-1) (chữ số đầu 1-9, các chữ số còn lại chọn từ 9 chữ số còn lại).
5. Đếm các số cùng độ dài với N: duyệt từng vị trí i, thử đặt chữ số nhỏ hơn arr[i] (và chưa dùng), cộng A(9-i, n-i-1). Nếu arr[i] đã dùng thì dừng.
6. Kết quả = N - count_unique.

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int A(int m, int n){
        int ret = 1;
        for (int i = 0; i < n; i++) { ret *= m; m--; }
        return ret;
    }
    int numDupDigitsAtMostN(int N){
        vector<int> arr;
        for (int i = N + 1; i > 0; i /= 10) arr.insert(arr.begin(), i % 10);
        int ret = 0;
        int n = arr.size();
        for (int i = 1; i < n; i++) ret += 9 * A(9, i - 1);
        set<int> visited;
        for (int i = 0; i < n; i++) {
            int digit = arr[i];
            for (int j = (i == 0 ? 1 : 0); j < digit; j++) {
                if (visited.count(j)) continue;
                ret += A(9 - i, n - i - 1);
            }
            if (visited.count(digit)) break;
            visited.insert(digit);
        }
        return N - ret;
    }
};
int main(){
    Solution ob;
    cout << (ob.numDupDigitsAtMostN(99));
}

Đầu vào

99

Đầu ra

9