এই সমস্যায়, আমাদেরকে n উপাদানগুলির সমন্বয়ে একটি অ্যারে অ্যারে দেওয়া হয়েছে যা হয় 0 বা 1। আমাদের কাজ হল প্রতিবেশীদের পূরণ করার ন্যূনতম পুনরাবৃত্তি ব্যবহার করে 1 দিয়ে অ্যারে পূরণ করা।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট: arr[] ={0, 1, 1, 0, 0, 1}
আউটপুট: 1
সমাধান পদ্ধতি -
সমস্যা সমাধানের জন্য, আমাদের এই সত্যটি জানতে হবে যে 1 একটি অবস্থানে উপস্থিত থাকলে এটি দুটি প্রতিবেশী 0 কে 1 এ রূপান্তর করতে পারে।
যদি, arr[i] হয় 1.
তারপর, arr[i-1] এবং arr[i+1] 1 এ রূপান্তরিত হবে।
এটি ব্যবহার করে, এই ক্ষেত্রে −
ব্যবহার করে সমাধান পাওয়া যাবেকেস 1: ব্লকের শুরুতে এবং শেষে 1 আছে। বাকি সব মান 0। শূন্যের সংখ্যা গণনা করুন।
পুনরাবৃত্তির সংখ্যা =জিরোকাউন্ট / 2 যদি গণনা সমান হয়
পুনরাবৃত্তির সংখ্যা =(শূন্যসংখ্যা -1)/2 যদি গণনা বিজোড় হয়
কেস 2: ব্লকের শুরুতে বা শেষে ব্লকের একক 1 আছে এবং বাকি সব মান 0।
পুনরাবৃত্তির সংখ্যা =শূন্য গণনা
কেস 3: ব্লকের কোন 1 নেই। প্রিন্ট -1 নির্দেশ করে 1 এর ফিলিং সম্ভব নয়।
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#include<iostream>
using namespace std;
int countIterationFill1(int arr[], int n) {
bool oneFound = false;
int iterationCount = 0;
for (int i=0; i<n; ) {
if (arr[i] == 1)
oneFound = true;
while (i<n && arr[i]==1)
i++;
int zeroCount = 0;
while (i<n && arr[i]==0) {
zeroCount++;
i++;
}
if (oneFound == false && i == n)
return -1;
int itrCount;
if (i < n && oneFound == true) {
if (zeroCount & 1 == 0)
itrCount = zeroCount/2;
else
itrCount = (zeroCount+1)/2;
zeroCount = 0;
}
else{
itrCount = zeroCount;
zeroCount = 0;
}
iterationCount = max(iterationCount, itrCount);
}
return iterationCount;
}
int main() {
int arr[] = {0, 1, 1, 0, 0, 1, 0, 0, 0, 1};
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The number of iterations to fill 1's is "<<countIterationFill1(arr, n);
return 0;
} আউটপুট −
The number of iterations to fill 1's is 2
