ধারণা
0s এবং 1s-এর একটি প্রদত্ত অ্যারের সাপেক্ষে, 1-এর সর্বোচ্চ ক্রমাগত ক্রম পেতে 0-এর অবস্থানটি 1 দিয়ে প্রতিস্থাপন করতে হবে। এই ক্ষেত্রে, প্রত্যাশিত সময়ের জটিলতা হল O(n) এবং সহায়ক স্থান হল O(1)।
ইনপুট
arr[] = {1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1} আউটপুট
Index 10
ধরুন অ্যারে সূচী 0 থেকে শুরু হয়, 0 এর পরিবর্তে 1-এ
সূচক 10 1s এর দীর্ঘতম অবিচ্ছিন্ন ক্রম সৃষ্টি করে।
ইনপুট
arr[] = {1, 1, 1, 1, 1, 0} আউটপুট
Index 5
পদ্ধতি
শূন্য-
-এর উভয় পাশের সংখ্যা ব্যবহার করাএখন, ধারণাটি হল প্রতিটি শূন্যের উভয় পাশের সংখ্যা গণনা করা। এখানে, প্রয়োজনীয় সূচকটিকে শূন্যের সূচক হিসাবে বিবেচনা করা হয় যার চারপাশে সর্বাধিক সংখ্যক রয়েছে। নিম্নলিখিত ভেরিয়েবলগুলি এই উদ্দেশ্য সম্পর্কিত প্রয়োগ করা হয়েছে -
- leftCnt − এটি বর্তমান উপাদান শূন্য আন্ডারসেনারেশনের বাম দিকের সংখ্যা সংরক্ষণ করতে ব্যবহৃত হয়।
- rightCnt − এটি বর্তমান উপাদান শূন্য আন্ডারবিবেচনার ডান দিকের সংখ্যা সংরক্ষণ করতে ব্যবহৃত হয়।
- ম্যাক্স ইনডেক্স - এটিকে শূন্যের সূচক হিসাবে বিবেচনা করা হয় যার চারপাশে সর্বাধিক সংখ্যক রয়েছে।
- lastInd − এটিকে দেখা শেষ শূন্য উপাদানের সূচক হিসাবে ধরা হয়
- maxCnt − যদি সূচক maxInd-এ শূন্য একটি দ্বারা প্রতিস্থাপিত হয় তবে এটিকে গণনা হিসাবে গণ্য করা হয়।
এখন পদ্ধতির বিস্তারিত নিচে দেওয়া হল -
-
ইনপুট অ্যারেতে একটি উপস্থিত না হওয়া পর্যন্ত বৃদ্ধির অধিকার বজায় রাখুন। অনুমান করুন পরবর্তী শূন্য সূচক i এ উপস্থিত।
-
এই শূন্য উপাদানটি প্রথম শূন্য উপাদান কিনা তা যাচাই করুন। এখন এটিকে প্রথম শূন্য উপাদান হিসেবে গণ্য করা হয় যদি লাস্টইন্ড কোনো বৈধ সূচক মান না রাখে।
-
তাই সেক্ষেত্রে লাস্টইন্ড আপডেট করা হয় i দিয়ে। বর্তমানে rightCnt-এর মান হল এই শূন্যের বাম পাশে শূন্যের সংখ্যা।
-
এর ফলে leftCnt হয় rightCnt এর সমান এবং তারপর আবার rightCnt এর মান নির্ধারণ করে। এটা দেখা গেছে যে যদি বর্তমান শূন্য উপাদানটি প্রথম শূন্য না হয়, তাহলে সূচক LastInd-এ উপস্থিত শূন্যের কাছাকাছি সংখ্যাগুলি leftCnt + rightCnt দ্বারা প্রদান করা হয়।
-
এখন maxCnt মান leftCnt + rightCnt + 1 এবং maxIndex =lastInd গ্রহণ করবে যদি এই মানটি বর্তমানে maxCnt দ্বারা ধারণ করা মানের থেকে ছোট হয়।
-
বর্তমানে rightCnt সূচী i-এ শূন্যের জন্য leftCnt হবে এবং lastInd হবে i-এর সমান। এখন আবার rightCnt এর মান নির্ধারণ করুন, maxCnt এর সাথে সংখ্যার তুলনা করুন এবং সেই অনুযায়ী maxCnt এবং maxIndex আপডেট করুন।
-
অ্যারের প্রতিটি পরবর্তী শূন্য উপাদানের জন্য আমাদের এই পদ্ধতিটি পুনরাবৃত্তি করতে হবে।
-
এটা লক্ষ্য করা গেছে যে লাস্টইন্ড শূন্যের সূচী সঞ্চয় করে যার জন্য বর্তমান leftCnt এবং rightCnt গণনা করা হয়।
-
অবশেষে, শূন্যের প্রয়োজনীয় সূচীটিকে একটি দিয়ে প্রতিস্থাপন করার জন্য maxIndex-এ সংরক্ষণ করা হয়।
উদাহরণ
// C++ program to find index of zero
// to be replaced by one to get longest
// continuous sequence of ones.
#include <bits/stdc++.h>
using namespace std;
// Used to returns index of 0 to be replaced
// with 1 to get longest continuous
// sequence of 1s. If there is no 0
// in array, then it returns -1.
int maxOnesIndex(bool arr1[], int n1){
int i = 0;
// Used to store count of ones on left
// side of current element zero
int leftCnt1 = 0;
// Used to store count of ones on right
// side of current element zero
int rightCnt1 = 0;
// Shows index of zero with maximum number
// of ones around it.
int maxIndex1 = -1;
// Shows index of last zero element seen
int lastInd1 = -1;
// Shows count of ones if zero at index
// maxInd1 is replaced by one.
int maxCnt1 = 0;
while (i < n1) {
// Used to keep incrementing count until
// current element is 1.
if (arr1[i]) {
rightCnt1++;
}
else {
// It has been observed that if current zero element
// is not first zero element,
// then count number of ones
// obtained by replacing zero at
// index lastInd. Update maxCnt
// and maxIndex if required.
if (lastInd1 != -1) {
if (rightCnt1 + leftCnt1 + 1 > maxCnt1) {
maxCnt1 = leftCnt1 + rightCnt1 + 1;
maxIndex1 = lastInd1;
}
}
lastInd1 = i;
leftCnt1 = rightCnt1;
rightCnt1 = 0;
}
i++;
}
// Determine number of ones in continuous
// sequence when last zero element is
// replaced by one.
if (lastInd1 != -1) {
if (leftCnt1 + rightCnt1 + 1 > maxCnt1) {
maxCnt1 = leftCnt1 + rightCnt1 + 1;
maxIndex1 = lastInd1;
}
}
return maxIndex1;
}
// Driver function
int main(){
bool arr1[] = { 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1 };
// bool arr1[] = {1, 1, 1, 1, 1, 0};
int n1 = sizeof(arr1) / sizeof(arr1[0]);
cout << "Index of 0 to be replaced is "
<< maxOnesIndex(arr1, n1);
return 0;
} আউটপুট
Index of 0 to be replaced is 10
