এই সমস্যায়, আমাদের একটি অ্যারে arr দেওয়া হয়েছে যাতে n সংখ্যক এলিমেন্ট আছে, যেগুলো হয় ০ অথবা ১। আমাদের কাজ হলো ন্যূনতম ইটারেশনে নেয়াবর ফিল করে অ্যারেকে ১ দিয়ে পূরণ করা।
উদাহরণ দিয়ে সমস্যাটি বোঝা যাক
ইনপুট: arr[] = {0, 1, 1, 0, 0, 1}
আউটপুট: 1
সমাধানের পদ্ধতি
এই সমস্যাটি সমাধান করতে আমাদের জানতে হবে যে, যদি কোনো পজিশনে ১ থাকে, তবে সেটি তার দুটি প্রতিবেশী ০ কে ১-এ রূপান্তর করতে পারে।
যদি, arr[i] হলো ১।
তবে, arr[i-1] এবং arr[i+1] ১-এ রূপান্তরিত হবে।
এই ব্যবহার করে সমাধান নিচের কেসগুলো দিয়ে পাওয়া যায়:
কেস ১: ব্লকে শুরু এবং শেষে ১ আছে। বাকি সব মান ০। শূন্যের সংখ্যা গণনা করুন।
ইটারেশনের সংখ্যা = zeroCount / 2 যদি কাউন্ট জোড় হয়
ইটারেশনের সংখ্যা = (zeroCount - 1) / 2 যদি কাউন্ট বিজোড় হয়
কেস ২: ব্লকে শুরু বা শেষে একক ১ আছে এবং বাকি সব মান ০।
ইটারেশনের সংখ্যা = zeroCount
কেস ৩: ব্লকে কোনো ১ নেই। -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
