दिए गए समस्या में, हमें 0 और 1 से बनी एक स्ट्रिंग दी गई है; हमें उन परम्यूटेशन की कुल संख्या निकालनी है जिनमें स्ट्रिंग 1 से शुरू होती है। चूंकि उत्तर बहुत बड़ा हो सकता है, इसलिए हम इसे 1000000007 से मोड्यूलो करके प्रिंट करते हैं।
इनपुट: str = "10101001001" आउटपुट: 210 इनपुट: str = "101110011" आउटपुट: 56
हम इस समस्या को कॉम्बिनेटोरिक्स और कुछ सूत्र बनाकर हल करेंगे।
समाधान खोजने का दृष्टिकोण
इस दृष्टिकोण में, हम स्ट्रिंग में 0 और 1 की संख्या गिनेंगे। मान लें n स्ट्रिंग में मौजूद 1 की संख्या है और m 0 की संख्या है, और L दी गई स्ट्रिंग की लंबाई है, तो इस समस्या को हल करने के लिए हमारा सूत्र होगा (L-1)! / (n-1)! * m!।
उदाहरण
#include <bits/stdc++.h> #define MOD 1000000007 // 1e9 + 7 को MOD परिभाषित करना using namespace std; long long fact(long long n) { if(n <= 1) return 1; return ((n % MOD) * (fact(n-1) % MOD)) % MOD; } int main() { string s = "101110011"; long long L = s.size(); // दी गई स्ट्रिंग की लंबाई long long count_1 = 0, count_0 = 0; // 1 और 0 की गिनती for(auto x : s) { if(x == '1') count_1++; // 1 की फ्रीक्वेंसी else count_0++; // 0 की फ्रीक्वेंसी } if(count_1 == 0){ cout << "0\n"; // यदि स्ट्रिंग में केवल 0 हैं तो उत्तर 0 होगा } else { long long factL = fact(L-1); // (L-1)! long long factn = fact(count_1 - 1); // (n-1)! long long factm = fact(count_0); // m! long long ans = factL / (factn * factm); // सूत्र लागू करना cout << ans << "\n"; } return 0; }आउटपुट
56
दिए गए प्रोग्राम की समय जटिलता O(N) है, जहां N दी गई स्ट्रिंग की लंबाई है।
उपरोक्त कोड की व्याख्या
इस दृष्टिकोण में, हम अपनी स्ट्रिंग के अंदर मौजूद 1 और 0 की संख्या गिन रहे हैं, अब हम शुरुआत में एक 1 रखते हैं और फिर शेष L-1 लंबाई की स्ट्रिंग में 0 और 1 के सभी संभावित परम्यूटेशन बनाते हैं, जिससे हमें (L-1)! / (n-1)! * m! का सूत्र मिलता है। जहां (n-1)! शेष 1 के परम्यूटेशन हैं, और m! 0 के परम्यूटेशन हैं।
निष्कर्ष
इस लेख में, हमने बाइनरी स्ट्रिंग के 1 से शुरू होने वाले यूनिक परम्यूटेशन की संख्या निकालने की समस्या को कॉम्बिनेटोरिक्स लगाकर और सूत्र बनाकर हल किया। हमने इस समस्या के लिए C++ प्रोग्राम और पूरा दृष्टिकोण भी सीखा। हम यही प्रोग्राम C, Java, Python आदि अन्य भाषाओं में भी लिख सकते हैं। आशा है आपको यह लेख उपयोगी लगा होगा।
