हमें बाइनरी नंबरों की एक स्ट्रिंग दी गई है यानी 0 और 1 का संयोजन और एक पूर्णांक मान k और कार्य दिए गए बाइनरी स्ट्रिंग के साथ k 1 के दिए गए सबस्ट्रिंग की गणना करना है।
इनपुट - स्ट्रिंग स्ट्र ='10000100000', के =2
आउटपुट − K वाले बाइनरी स्ट्रिंग के सबस्ट्रिंग की संख्या है − 6
स्पष्टीकरण - दिए गए स्ट्रिंग से बनने वाले सबस्ट्रिंग्स 1, 10, 100, 1000, 10000, 010, 100001, 10001, 1001, 101, 11, 1000010 हैं। इसलिए 6 सबस्ट्रिंग हैं जिनमें 1 की k संख्या है, यानी ठीक 2 वाले।
इनपुट - स्ट्रिंग str ='10000100000’, k =3
आउटपुट − K वाले बाइनरी स्ट्रिंग के सबस्ट्रिंग की संख्या है − 0
स्पष्टीकरण - हमें k के पूर्णांक मान के साथ 3 दिया गया है और यदि हम बाइनरी संख्याओं वाले हमारे स्ट्रिंग की जांच करते हैं, तो इसमें केवल 2 होते हैं। इसलिए k संख्या दिए जाने पर प्रतिस्थापन की कोई संभावना नहीं है।
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
-
0 और 1 के संयोजन और एक पूर्णांक चर k वाले बाइनरी नंबरों की एक स्ट्रिंग इनपुट करें।
-
लंबाई () फ़ंक्शन का उपयोग करके स्ट्रिंग की लंबाई की गणना करें और आगे की प्रक्रिया के लिए डेटा को फ़ंक्शन में पास करें।
-
k के साथ सबस्ट्रिंग को संग्रहीत करने के लिए एक अस्थायी चर गणना और कुल को 0 के रूप में घोषित करें।
-
आकार वाले लोगों की आवृत्ति को स्ट्रिंग प्लस वन की लंबाई के रूप में संग्रहीत करने के लिए एक सरणी घोषित करें और इसे 0 से प्रारंभ करें और सरणी के पहले तत्व को 1 के रूप में सेट करें।
-
0 से एक सरणी की लंबाई तक के लिए लूप प्रारंभ करें
-
लूप के अंदर, टोटल को टोटल + str[i] - '0' के रूप में सेट करें। IF टोटल>=k चेक करें, फिर काउंट को काउंट + arr[total-k] के रूप में सेट करें।
-
वापसी की संख्या
-
परिणाम प्रिंट करें।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int sub_k_ones(string str, int length, int k){
int count = 0;
int total_1 = 0;
int arr_fre[length + 1] = {0};
arr_fre[0] = 1;
for (int i = 0; i < length; i++){
total_1 = total_1 + (str[i] - '0');
if (total_1 >= k){
count = count + arr_fre[total_1 - k];
}
arr_fre[total_1]++;
}
return count;
}
int main(){
string str = "10000100000";
int length = str.length();
int k = 2;
cout<<"Count of substrings of a binary string containing K ones are: "<<sub_k_ones(str, length, k) << endl;
return 0;
} आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा -
Count of substrings of a binary string containing K ones are: 6