সমস্যা বিবৃতি
n ধনাত্মক পূর্ণসংখ্যা এবং একটি সংখ্যা k এর একটি অ্যারে দেওয়া হয়েছে। k-এর থেকে কম বা সমান সমস্ত সংখ্যা একসাথে আনতে প্রয়োজনীয় ন্যূনতম সংখ্যক অদলবদল খুঁজুন।
উদাহরণ
যদি ইনপুট অ্যারে ={1, 5, 4, 7, 2, 10} এবং k =6 হয়, তাহলে 1 অদলবদল প্রয়োজন, অর্থাৎ 2 এর সাথে সোয়াপ উপাদান 7।
অ্যালগরিদম
- সমস্ত উপাদান গণনা করুন যা 'k' এর থেকে কম বা সমান। ধরা যাক গণনা হল 'cnt'
- 'cnt' দৈর্ঘ্যের উইন্ডোর জন্য দুটি পয়েন্টার কৌশল ব্যবহার করে, প্রতিবার এই পরিসরে কতগুলি উপাদান 'k'-এর থেকে বড় তা ট্র্যাক করুন। ধরা যাক মোট গণনা হল 'outOfRange'৷ ৷
- প্রত্যেক দৈর্ঘ্যের 'cnt' উইন্ডোর জন্য ধাপ 2 পুনরাবৃত্তি করুন এবং তাদের মধ্যে ন্যূনতম গণনা '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
