C++-এ পুনরাবৃত্ত ডিজিট বিশিষ্ট সংখ্যার গণনা

সমস্যা বিবরণ

একটি ধনাত্মক পূর্ণসংখ্যা N দেওয়া থাকলে, ১ থেকে N পর্যন্ত কতগুলো সংখ্যা কমপক্ষে একটি ডিজিট পুনরাবৃত্ত হয়েছে তা বের করতে হবে।

উদাহরণ

N = 99 → আউটপুট = 9 (সঙ্গে: 11, 22, 33, 44, 55, 66, 77, 88, 99)

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

পূরক গণনা (Complementary Counting): নন-রিপিটিং ডিজিট বিশিষ্ট সংখ্যাগুলো বের করে N থেকে বিয়োগ করুন।
A(m, n) ফাংশন দিয়ে পারমুটেশন গণনা করা হয়।
N+1 কে ডিজিট আরেে রূপান্তর করে প্রসেস করা হয়।
ভিজিটেড সেট দিয়ে ডিজিট পুনরাবৃত্তি ট্র্যাক করা হয়।

C++ বাস্তবায়ন

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

class Solution {
    int A(int m, int n) {
        int ret = 1;
        for (int i = 0; i < n; i++) {
            ret *= m;
            m--;
        }
        return ret;
    }
    
public:
    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, 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);
    return 0;
}

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

ইনপুট: 99

আউটপুট: 9