সমস্যা বিবরণ
একটি অ্যারে দেওয়া আছে যাতে শুধু ০ এবং ১ রয়েছে। সকল ১ একসাথে আনার জন্য ন্যূনতম সোয়াপ সংখ্যা বের করতে হবে। উদাহরণ: {1, 0, 1, 1, 0, 1} এর জন্য ১টি সোয়াপ (প্রথম ০ এবং শেষ ১ সোয়াপ)।
অ্যালগরিদম
- অ্যারেতে মোট কতগুলো ১ আছে তা গণনা করুন (মান x)।
- দৈর্ঘ্য x-এর সাবঅ্যারে যেটিতে সর্বাধিক ১ আছে তা খুঁজুন।
- সাবঅ্যারেটিতে থাকা ০-এর সংখ্যাই ন্যূনতম সোয়াপ।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int getMinSwaps(int *arr, int n) {
int oneCnt = 0;
for (int i = 0; i < n; ++i)
if (arr[i] == 1) ++oneCnt;
int x = oneCnt;
int maxOnes = INT_MIN;
int preCompute[n] = {0};
if (arr[0] == 1) preCompute[0] = 1;
for (int i = 1; i < n; ++i) {
if (arr[i] == 1) preCompute[i] = preCompute[i-1] + 1;
else preCompute[i] = preCompute[i-1];
}
for (int i = x-1; i < n; ++i) {
int currOnes = (i == x-1) ? preCompute[i] : preCompute[i] - preCompute[i-x];
if (maxOnes < currOnes) maxOnes = currOnes;
}
return x - maxOnes;
}
int main() {
int arr[] = {1, 0, 1, 1, 0, 1};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Minimum swap count = " << getMinSwaps(arr, n) << endl;
return 0;
}
আউটপুট
Minimum swap count = 1
