আমাদেরকে বাইনারি সংখ্যার একটি স্ট্রিং দেওয়া হয়েছে যেমন 0 এবং 1 এর সমন্বয় এবং একটি পূর্ণসংখ্যা মান k এবং কাজটি হল k 1 দেওয়া প্রদত্ত বাইনারি স্ট্রিং দিয়ে গঠিত সাবস্ট্রিংগুলির গণনা করা।
ইনপুট − স্ট্রিং str ='10000100000', k =2
আউটপুট − K যুক্ত একটি বাইনারি স্ট্রিং এর সাবস্ট্রিং এর সংখ্যা হল − 6
ব্যাখ্যা − প্রদত্ত স্ট্রিং থেকে যে সাবস্ট্রিংগুলি তৈরি করা যেতে পারে তা হল 1, 10, 100, 1000, 10000, 010, 100001, 10001, 1001, 101, 11, 1000010৷ তাই 6টি সাবস্ট্রিং রয়েছে যার i1 এর k একটি সংখ্যা রয়েছে৷
ইনপুট − স্ট্রিং str ='10000100000', k =3
আউটপুট − K যুক্ত একটি বাইনারি স্ট্রিং এর সাবস্ট্রিং এর সংখ্যা হল − 0
ব্যাখ্যা − আমাদের 3 হিসাবে k এর একটি পূর্ণসংখ্যার মান দেওয়া হয়েছে এবং যদি আমরা বাইনারি সংখ্যা ধারণকারী আমাদের স্ট্রিংটি পরীক্ষা করি তবে এতে শুধুমাত্র 2টি আছে। সুতরাং k নম্বর দিলে সাবস্ট্রিং হওয়ার কোনো সম্ভাবনা নেই।
নিচের প্রোগ্রামে ব্যবহৃত পদ্ধতিটি নিম্নরূপ
-
বাইনারি সংখ্যার একটি স্ট্রিং ইনপুট করুন যেখানে 0 এবং 1 এর সমন্বয় এবং একটি পূর্ণসংখ্যা পরিবর্তনশীল k।
-
length() ফাংশন ব্যবহার করে স্ট্রিংয়ের দৈর্ঘ্য গণনা করুন এবং আরও প্রক্রিয়াকরণের জন্য ফাংশনে ডেটা পাস করুন।
-
একটি অস্থায়ী পরিবর্তনশীল গণনা ঘোষণা করুন এবং k এর সাথে সাবস্ট্রিংগুলি সংরক্ষণ করার জন্য মোট 0 হিসাবে ঘোষণা করুন৷
-
স্ট্রিং প্লাস ওয়ানের দৈর্ঘ্যের আকারের ফ্রিকোয়েন্সি সংরক্ষণ করতে একটি অ্যারে ঘোষণা করুন এবং এটি 0 দিয়ে শুরু করুন এবং অ্যারের প্রথম উপাদানটি 1 হিসাবে সেট করুন।
-
স্টার্ট লুপ ফর 0 থেকে একটি অ্যারের দৈর্ঘ্য পর্যন্ত
-
লুপের ভিতরে, total + str[i] - '0' হিসাবে সেট করুন। IF total>=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
