C++-এ ডিজিট সেট দিয়ে N পর্যন্ত সংখ্যা গণনা

সমস্যা বিবরণ

সর্টেড ডিজিট সেট D (১-৯ থেকে, ০ ছাড়া) দেওয়া থাকলে, D-এর ডিজিটগুলো যেকোনো বার ব্যবহার করে N-এর চেয়ে ছোট বা সমান কতগুলো পূর্ণসংখ্যা বানানো যায় তা বের করতে হবে।

উদাহরণ

D = [2,3,4,7], N = 100 → আউটপুট = 20 (সংখ্যা: 2,3,4,7,22,23,24,27,32,33,34,37,42,43,44,47,72,73,74,77)

সমাধান পদ্ধতি

N-এর ডিজিট সংখ্যা কম হলে সরাসরি D.size()^length যোগ করা হয়।
N-এর প্রতিটি ডিজিটের জন্য D-র ছোট ডিজিটগুলো দিয়ে কাউন্ট করা হয়।
সেম ডিজিট পাওয়া গেলে পরবর্তী ডিজিটে যাওয়া হয়, না পেলে ব্রেক।
শেষে N নিজেও বৈধ হলে +1 করা হয়।

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(), 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);
    return 0;
}

ইনপুট ও আউটপুট

ইনপুট: {"2","3","4","7"}, 100

আউটপুট: 20