मान लीजिए हमारे पास स्ट्रिंग 'str' की लंबाई और एक स्ट्रिंग दी गई है। कार्य दिए गए बाइनरी स्ट्रिंग में उन सबस्ट्रिंग्स की संख्या गिनना है जो '1' से शुरू होती हैं और '1' पर खत्म होती हैं। एक बाइनरी स्ट्रिंग में केवल '1' और '0' होते हैं। उदाहरण के लिए,
इनपुट-1 -
N = 5 str = '11101'
आउटपुट -
6
व्याख्या - दी गई बाइनरी स्ट्रिंग में, हमारे पास 6 सबस्ट्रिंग्स हैं जो '1' से शुरू होती हैं और '1' पर खत्म होती हैं। इन सबस्ट्रिंग्स का सेट {'11', '111', '1110', '11101', '1101', '101'} है।
इनपुट-1 -
N = 4 str = '0011'
आउटपुट -
1
व्याख्या -
दी गई बाइनरी स्ट्रिंग में हमारे पास 1 सबस्ट्रिंग है जो '1' से शुरू होती है और '1' पर खत्म होती है। इन सबस्ट्रिंग्स का सेट एक सिंगलटन सेट है यानी, {'11'}।
इस प्रॉब्लम को हल करने के लिए उपयोग किया गया दृष्टिकोण
दी गई स्ट्रिंग के लिए, हमें उन सबस्ट्रिंग्स की संख्या गिननी है जो '1' से शुरू होती हैं और '1' पर खत्म होती हैं। यह प्रॉब्लम प्रसिद्ध हैंडशेक प्रॉब्लम के समान है जिसमें हमें 'n' लोगों की पार्टी में हैंडशेक की संख्या गिननी होती है।
यदि हम दी गई स्ट्रिंग में 1 की संख्या गिनते हैं, तो हम उन सबस्ट्रिंग्स का सेट ढूंढ सकते हैं जो '1' से शुरू होती हैं और '1' पर खत्म होती हैं।
N लंबाई की एक स्ट्रिंग का इनपुट लें।
एक पूर्णांक फंक्शन countSubstring(int N, string s) स्ट्रिंग की लंबाई और एक स्ट्रिंग को इनपुट के रूप में लेता है और उन सभी सबस्ट्रिंग्स की गिनती लौटाता है जो '1' से शुरू होती हैं और '1' पर खत्म होती हैं।
पूरी स्ट्रिंग पर पुनरावृति करें और स्ट्रिंग में '1' की संख्या गिनें।
दिए गए स्ट्रिंग में सबस्ट्रिंग्स (जोड़े) की संख्या n*(n-1)/2 द्वारा गिनें।
n*(n-1)/2 का परिणाम लौटाएं।
उदाहरण
#include <iostream>
using namespace std;
int countSubstring(int N, string s) {
int count = 0;
for (int i = 0; s[i] != '\0'; ++i) {
if (s[i] == '1')
count++;
}
return count * (count - 1) / 2;
}
int main() {
int N = 5;
string str = "11101";
cout << countSubstring(N, str) << endl;
return 0;
}
आउटपुट
यदि हम उपरोक्त कोड चलाएंगे तो यह आउटपुट के रूप में प्रिंट करेगा,
6
चूंकि दी गई स्ट्रिंग में मौजूद '1' की संख्या '4' है यानी, काउंट = 4, '1' से शुरू और '1' पर खत्म होने वाली सबस्ट्रिंग्स की कुल संख्या हैं, 4*(4-1)/2 = 6।
