ধরুন, আমাদের কাছে N উপাদানের একটি অ্যারে আছে। এই উপাদানগুলি হয় 0 বা 1। 1 এর দীর্ঘতম সংলগ্ন ক্রম পেতে 0 এর অবস্থানটি 1 দিয়ে প্রতিস্থাপন করুন। ধরুন অ্যারেটি arr =[1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1] এর মতো, আউটপুট সূচক হল 9। সূচক 9-এ 1-এর সাথে 0 প্রতিস্থাপন করলে সর্বাধিক সংলগ্ন ক্রম 1s
আমাদের তিনটি সূচকের ট্র্যাক রাখতে হবে। বর্তমান সূচক (curr), পূর্ববর্তী শূন্য সূচক (pz), এবং পূর্ববর্তী থেকে পূর্ববর্তী শূন্য সূচক (ppz)। এখন অ্যারেটি অতিক্রম করুন যখন অ্যারে উপাদান 0 হয়, তারপর curr এবং ppz-এর মধ্যে পার্থক্য গণনা করুন, যদি পার্থক্য সর্বাধিকের চেয়ে বেশি হয়, তাহলে সর্বাধিক আপডেট করুন, অবশেষে সর্বাধিক পার্থক্য সহ prev_zero-এর সূচক ফেরত দিন।
উদাহরণ
#include<iostream>
using namespace std;
int findIndex(bool arr[], int n) {
int count_max = 0;
int index;
int pz = -1;
int ppz = -1;
for (int curr=0; curr<n; curr++) {
if (arr[curr] == 0) {
if (curr - ppz > count_max){
count_max = curr - ppz;
index = pz;
}
ppz = pz;
pz = curr;
}
}
if (n-ppz > count_max)
index = pz;
return index;
}
int main() {
bool arr[] = {1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Index of 0 to be replaced is "<< findIndex(arr, n);
} আউটপুট
Index of 0 to be replaced is 9
