সমস্যা বিবরণ
n সংখ্যক ধনাত্মক পূর্ণসংখ্যার অ্যারে এবং একটি সংখ্যা k দেওয়া আছে। k-এর চেয়ে ছোট বা সমান সব সংখ্যাকে একসাথে আনার জন্য ন্যূনতম সোয়াপ বের করতে হবে। উদাহরণ: {1, 5, 4, 7, 2, 10}, k=6 হলে ১টি সোয়াপ (7 এবং 2 সোয়াপ)।
অ্যালগরিদম
- k-এর চেয়ে ছোট বা সমান উপাদানগুলোর মোট সংখ্যা গণনা করুন (cnt)।
- দুটি পয়েন্টার বা স্লাইডিং উইন্ডো ব্যবহার করে দৈর্ঘ্য cnt-এর উইন্ডোতে কতগুলো উপাদান k-এর চেয়ে বড় আছে তা ট্র্যাক করুন (outOfRange)।
- প্রতিটি উইন্ডোর জন্য outOfRange-এর মিনিমাম মানই উত্তর।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int getMinSwaps(int *arr, int n, int k) {
int cnt = 0;
for (int i = 0; i < n; ++i)
if (arr[i] <= k) ++cnt;
int outOfRange = 0;
for (int i = 0; i < cnt; ++i)
if (arr[i] > k) ++outOfRange;
int result = outOfRange;
for (int i = 0, j = cnt; j < n; ++i, ++j) {
if (arr[i] > k) --outOfRange;
if (arr[j] > k) ++outOfRange;
result = min(result, outOfRange);
}
return result;
}
int main() {
int arr[] = {1, 5, 4, 7, 2, 10};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 6;
cout << "Minimum swaps = " << getMinSwaps(arr, n, k) << endl;
return 0;
}
আউটপুট
Minimum swaps = 1
