Số lượng số tối đa N cho tập chữ số cho trước trong C++

Cho tập chữ số D (không chứa 0). Viết các số dùng chữ số trong D (có thể lặp). Đếm số lượng số dương ≤ N.

Ví dụ: D=[2,3,4,7], N=100 → 20.

Giải thuật

1. Đếm các số có ít chữ số hơn N: với độ dài i từ 1 đến len(N)-1, cộng |D|^i.
2. Đếm các số cùng độ dài với N: duyệt từng vị trí i, đếm số chữ số trong D nhỏ hơn N[i], mỗi cái cộng |D|^(len-i-1). Nếu N[i] không có trong D thì dừng. Nếu duyệt hết thì cộng 1 (chính N).

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int atMostNGivenDigitSet(vector<string> &D, int N) {
        string n = to_string(N);
        int sz = n.size();
        int ret = 0;
        for (int i = 1; i < sz; i++) ret += pow(D.size(), i);
        for (int i = 0; i < sz; i++) {
            bool hasSameNum = false;
            for (string &x : D) {
                if (x[0] < n[i]) ret += pow(D.size(), sz - i - 1);
                else if (x[0] == n[i]) hasSameNum = true;
            }
            if (!hasSameNum) return ret;
        }
        return ret + 1;
    }
};
int main(){
    Solution ob;
    vector<string> v = {"2","3","4","7"};
    cout << (ob.atMostNGivenDigitSet(v, 100));
}

Đầu vào

{"2","3","4","7"}, 100

Đầu ra

20