N উপাদানের একটি অ্যারে দেওয়া আছে। উপাদানগুলো হয় ০ অথবা ১। ০ কে ১ দিয়ে রিপ্লেস করলে যেটি সর্বোচ্চ কনটিগুয়াস (contiguous) ১-এর সিকোয়েন্স দেবে, সেই ০-এর পজিশন খুঁজে বের করতে হবে। উদাহরণস্বরূপ, arr = [1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1] হলে আউটপুট ইনডেক্স ৯। ইনডেক্স ৯-এ ০ কে ১ করলে সর্বোচ্চ ১-এর সিকোয়েন্স পাওয়া যায়।
আমাদের তিনটি ইনডেক্স ট্র্যাক করতে হবে: কারেন্ট ইনডেক্স (curr), প্রিভিয়াস জিরো ইনডেক্স (pz), এবং প্রিভিয়াস টু প্রিভিয়াস জিরো ইনডেক্স (ppz)। এখন অ্যারে ট্রাভার্স করব, যখন অ্যারে এলিমেন্ট ০ পাওয়া যাবে, তবে curr এবং ppz-এর পার্থক্য ক্যালকুলেট করব। যদি পার্থক্য max-এর চেয়ে বড় হয়, তবে max আপডেট করব, অবশেষে max পার্থক্য দিয়ে যে 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
