दी गई समस्या में, हमें 0 और 1 की एक स्ट्रिंग दी गई है; हमें क्रमपरिवर्तन की कुल संख्या ज्ञात करनी है जैसे कि स्ट्रिंग 1 से शुरू होती है। चूंकि उत्तर एक बड़ी संख्या हो सकती है, इसलिए हम एक मॉड के रूप में 1000000007 के साथ प्रिंट करते हैं।
Input : str ="10101001001" Output : 210 Input : str ="101110011" Output : 56
हम इस समस्या को हल करने के लिए कुछ कॉम्बिनेटरिक्स लागू करके और कुछ सूत्रों का निर्माण करके दी गई समस्या का समाधान करेंगे।
समाधान खोजने के लिए दृष्टिकोण
दृष्टिकोण में, हम 0 और 1 की संख्या की गणना करेंगे। अब मान लीजिए n हमारे स्ट्रिंग में मौजूद 1 की संख्या है और m हमारे स्ट्रिंग में मौजूद 0 की संख्या है और L को हमारे दिए गए स्ट्रिंग की लंबाई होने दें, इसलिए इस समस्या को हल करने के लिए हम जो सूत्र बनाते हैं वह है (L-1) )!/ (एन-1)! * मी!.
उदाहरण
#include <bits/stdc++.h>
#define MOD 1000000007 // defining 1e9 + 7 as 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(); // length of given string
long long count_1 = 0, count_0 = 0; // keeping count of 1's and 0's
for(auto x : s) {
if(x == '1')
count_1++; // frequency of 1's
else
count_0++; // frequency of 0's
}
if(count_1 == 0){
cout << "0\n"; // if string only consists of 0's so our answer will be 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); // putting the formula
cout << ans << "\n";
}
return 0;
} आउटपुट
56
दिए गए प्रोग्राम में O(N) की समय जटिलता है, जहां n हमारे दिए गए स्ट्रिंग की लंबाई है।
उपरोक्त कोड की व्याख्या
इस दृष्टिकोण में, हम अपनी स्ट्रिंग के अंदर मौजूद 1 और 0 की संख्या की गणना कर रहे हैं, हम शुरुआत में एक रखते हैं और अब लंबाई एल -1 की स्ट्रिंग में 0 और 1 के सभी संभावित क्रमपरिवर्तन तैयार करते हैं, इसलिए इसे तैयार करके हम (L-1) का सूत्र प्राप्त करें! / (एन -1)! * एम! कहाँ (एन -1)! क्या शेष 1 और मी के क्रमपरिवर्तन हैं! 0 का क्रमपरिवर्तन है।
निष्कर्ष
इस लेख में, हम एक बाइनरी स्ट्रिंग के 1 से शुरू होने वाले अद्वितीय क्रमपरिवर्तन की संख्या को खोजने के लिए कुछ कॉम्बिनेटरिक्स को लागू करके और इसके लिए एक सूत्र बनाकर एक समस्या का समाधान करते हैं।
हमने इस समस्या के लिए C++ प्रोग्राम और संपूर्ण दृष्टिकोण (Normal) भी सीखा जिसके द्वारा हमने इस समस्या को हल किया। हम उसी प्रोग्राम को अन्य भाषाओं जैसे सी, जावा, पायथन और अन्य भाषाओं में लिख सकते हैं। हमें उम्मीद है कि आपको यह लेख मददगार लगा होगा।