परिचय
मान लीजिए हमारे पास एक पूर्णांक n है, हमें उन धनात्मक पूर्णांकों की संख्या ढूंढनी है जो n से कम या बराबर हैं, जहां पूर्णांक में कम से कम एक अंक एक से अधिक बार आता है।
तो, यदि इनपुट n = 200 है, तो आउटपुट 38 होगा।
समाधान दृष्टिकोण
यह समस्या "कम से कम एक डुप्लिकेट अंक वाली संख्याएं" गिनने के बराबर है। हम पूरक (complement) गिनते हैं: सभी अंक अलग-अलग वाली संख्याएं, फिर कुल से घटाते हैं।
उदाहरण कोड
#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;
}
इनपुट
200
आउटपुट
38
व्याख्या
1 से 200 तक 38 संख्याएं ऐसी हैं जिनमें कम से कम एक अंक दोहराता है। यह कॉम्बिनेटोरिक्स और बिटमास्किंग का उपयोग करके कुशलता से गणना करता है।
निष्कर्ष
यह अंक DP (Digit DP) समस्या का एक अनुकूलित समाधान है। बिटमास्क प्रयुक्त अंकों को ट्रैक करता है। यदि आपके कोई प्रश्न हैं, तो कमेंट सेक्शन में पूछें।
