C++-এ n-র চেয়ে ছোট বা সম এমন ইন্টিজার যাতে একই ডিজিট একাধিকবার থাকে

মান লইয়া আমাদের একটি ইন্টিজার n দেওয়া আছে, আমাদের বের করতে হবে কতগুলো পজিটিভ ইন্টিজার n-র চেয়ে ছোট বা সম যেখানে কমপক্ষে একটি ডিজিট একাধিকবার আছে।

তবে, যদি ইনপুট হয় n = 200, তবে আউটপুট হবে 38।

এটি সমাধান করতে, আমরা এই ধাপগুলো ফলো করব:

একটি অ্যারে a ডিফাইন করুন
x := n দিয়ে ইনিশিয়ালাইজ করুন, x নন-জিরো থাকা পর্যন্ত x := x / 10 আপডেট করে, a-তে x mod 10 পুশ করুন
অ্যারে a রিভার্স করুন
ret := n
w := 1, d := 1 দিয়ে ইনিশিয়ালাইজ করুন, w < a.size() থাকা পর্যন্ত w বাড়িয়ে যান:
- d := d * min(9, 10 - w + 1)
- ret := ret - d
go() ফাংশন ডিফাইন করুন। এটি কোনো আর্গুমেন্ট নেয় না।
- b := (1 << 10) - 1
- i := 0 থেকে a.size() পর্যন্ত:
  - d := (i < 1) থেকে a[i]-১ পর্যন্ত:
    - ret := ret - x
  - যদি ((1 << a[i]) & b) নন-জিরো হয়, তবে b := b ^ (1 << a[i])
  - অন্যথায় রিটার্ন
- ret --
go() কল করুন
ret রিটার্ন করুন

বेहतर বোঝার জন্য ইমপ্লিমেন্টেশন দেখুন:

উদাহরণ

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

int solve(int n) {
    vector<int> a;
    for (int x = n; x; x /= 10) a.push_back(x % 10);
    reverse(a.begin(), a.end());
    int ret = n;
    for (int w = 1, d = 1; w < a.size(); ++w) {
        d *= min(9, 10 - w + 1);
        ret -= d;
    }
    auto go = [&]() {
        int b = (1 << 10) - 1;
        for (int i = 0; i < a.size(); ++i) {
            for (int d = (i < 1); d < a[i]; ++d) {
                int x = 0;
                if ((1 << d) & b) ++x;
                for (int j = i + 1; j < a.size(); ++j) x *= 10 - j;
                ret -= x;
            }
            if ((1 << a[i]) & b)
                b ^= (1 << a[i]);
            else
                return;
        }
        --ret;
    };
    go();
    return ret;
}

int main(){
    cout << solve(200) << endl;
    return 0;
}