এই টিউটোরিয়ালে, আমরা অ্যারেতে পরপর 1 এর সর্বাধিক সংখ্যা পেতে শূন্যের সংখ্যা খুঁজে বের করতে যাচ্ছি।
আমরা সমস্যা সমাধানের জন্য স্লাইডিং উইন্ডো পদ্ধতি ব্যবহার করতে যাচ্ছি। আসুন সমস্যা সমাধানের পদক্ষেপগুলি দেখি৷
৷-
ফ্লিপ করার জন্য অ্যারে এবং সর্বাধিক শূন্য শুরু করুন।
-
দৈর্ঘ্য সহ সূচী শুরু, শেষের উইন্ডো শুরু করুন।
-
পরপর 1 এর দৈর্ঘ্য এবং প্রারম্ভিক সূচকের সর্বাধিক উপ-অ্যারে সংরক্ষণ করুন।
-
শেষ সূচকগুলি অ্যারের দৈর্ঘ্য অতিক্রম না করা পর্যন্ত অ্যারের উপর পুনরাবৃত্তি করুন৷
-
যদি শূন্যের সংখ্যা সর্বাধিক শূন্য গণনার চেয়ে কম হয় তাহলে শেষ সূচকটি বৃদ্ধি করুন এবং বর্তমান মান শূন্য হলে শূন্য গণনা করুন।
-
যদি শূন্যের সংখ্যা সর্বাধিক শূন্য গণনার চেয়ে বেশি হয় তাহলে প্রারম্ভিক সূচকটি বৃদ্ধি করুন এবং বর্তমান মান শূন্য হলে শূন্য গণনা হ্রাস করুন।
-
বর্তমান উইন্ডোর দৈর্ঘ্য আগেরটির থেকে বেশি হলে সর্বাধিক উইন্ডো আপডেট করুন।
-
অ্যারের উপর পুনরাবৃত্তি করুন এবং উইন্ডো প্রারম্ভিক সূচী ব্যবহার করে শূন্য সূচকগুলি মুদ্রণ করুন।
উদাহরণ
আসুন কোডটি দেখি।
#include <bits/stdc++.h>
using namespace std;
void zeroesIndexes(int arr[], int maxZeroes, int n) {
int start = 0, end = 0;
int zeroesCount = 0;
int bestWindowCount = 0, bestWindowStartIndex = 0;
while (end < n) {
if (zeroesCount <= maxZeroes) {
if (arr[end] == 0) {
zeroesCount++;
}
end++;
}
if (zeroesCount > maxZeroes) {
if (arr[start] == 0) {
zeroesCount--;
}
start++;
}
if ((end - start > bestWindowCount) && (zeroesCount <= maxZeroes)) {
bestWindowCount = end - start;
bestWindowStartIndex = start;
}
}
cout << "The indexes are ";
for (int i = 0; i < bestWindowCount; ++i) {
if(arr[bestWindowStartIndex + i] == 0)
cout << bestWindowStartIndex + i << " ";
}
}
int main() {
int arr[] = {1, 0, 0, 1, 1, 0, 1, 0, 1, 1};
int maxZeroes= 2;
zeroesIndexes(arr, maxZeroes, 10);
return 0;
} আউটপুট
আপনি যদি উপরের কোডটি চালান, তাহলে আপনি নিম্নলিখিত ফলাফল পাবেন।
The indexes are 5 7
উপসংহার
টিউটোরিয়ালে আপনার কোন প্রশ্ন থাকলে মন্তব্য বিভাগে উল্লেখ করুন।
