সমস্যা বিবরণ
শুধু ০ এবং ১ ধারণকারী n সাইজের একটি অ্যারে দেওয়া আছে। ন্যূনতম টগল (০ থেকে ১ বা ১ থেকে ০) খুঁজে বের করতে হবে যাতে অ্যারেটি পার্টিশনড হয়, অর্থাৎ আগে সব ০ তারপর সব ১ থাকে।
উদাহরণ
যদি arr[] = {1, 0, 0, 1, 1, 1, 0} হয়, তবে ২টি টগল প্রয়োজন: প্রথম ১ এবং শেষ ০ টগল করলে।
অ্যালগরিদম
- প্রশ্নটি গৌর করলে দেখা যাবে ০ থেকে n-1 পর্যন্ত অবশ্যই একটি পয়েন্ট থাকবে যার বামপাশে সব ০ এবং ডানপাশে সব ১ থাকবে।
- যে ইন্ডেক্সগুলো এই নিয়ম মানেন না, সেগুলো টগল করতে হবে। বাম থেকে ডানে ০ গুনতে হবে।
সি++ কোড উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int getMinToggles(int* arr, int n) {
int zeroCnt[n + 1] = {0};
for (int i = 1; i <= n; ++i) {
if (arr[i - 1] == 0)
zeroCnt[i] = zeroCnt[i - 1] + 1;
else
zeroCnt[i] = zeroCnt[i - 1];
}
int result = n;
for (int i = 1; i <= n; ++i)
result = min(result, i - zeroCnt[i] + zeroCnt[n] - zeroCnt[i]);
return result;
}
int main() {
int arr[] = {1, 0, 0, 1, 1, 1, 0};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Minimum toggles = " << getMinToggles(arr, n) << endl;
return 0;
}
আউটপুট
Minimum toggles = 2
