সমস্যা বিবরণ
Nটি ইন্টিজার এবং K দেওয়া আছে, ন্যূনতম কতগুলো এলিমেন্ট সরাতে হবে যাতে Amax - Amin <= K। এলিমেন্ট সরানোর পর Amax এবং Amin বাকি এলিমেন্টগুলোর মধ্যে থেকে বিবেচনা করা হবে।
উদাহরণ
arr[] = {1, 3, 4, 9, 10, 11, 12, 17, 20} এবং k = 4 হলে আউটপুট ৫:
- অ্যারের শুরু থেকে ১, ৩, ৪ সরান
- অ্যারের শেষ থেকে ১৭, ২০ সরান
- ফাইনাল অ্যারে: {9, 10, 11, 12} যেখানে 12 - 9 <= 4
অ্যালগরিদম
1. দেওয়া এলিমেন্টগুলো সর্ট করুন। 2. গ্রিডি পদ্ধতিতে, সেরা উপায় হলো ন্যূনতম বা সর্বোচ্চ এলিমেন্ট সরিয়ে চেক করা যে Amax - Amin <= K। রিমUভালের বিভিন্ন কম্বিনেশন বিবেচনা করতে হবে। 3. রিমUভালের দুটি সম্ভাব্য পথ: ন্যূনতম সরান অথবা সর্বোচ্চ সরান। Let(i...j) হোক রিমUভালের পর বাকি এলিমেন্টের ইনডেক্স। শুরুতে i=0, j=n-1 এবং রিমUভাল করা এলিমেন্ট ০। 4. শুধু তখনই এলিমেন্ট সরাব যখন a[j]-a[i]>k, দুটি সম্ভাব্য পথ: (i+1...j) বা (i...j-1)। দুটির ন্যূনতম নেওয়া হবে।
উদাহরণ
#include <bits/stdc++.h>
#define MAX 100
using namespace std;
int dp[MAX][MAX];
int removeCombinations(int *arr, int i, int j, int k) {
if (i >= j) {
return 0;
} else if ((arr[j] - arr[i]) <= k) {
return 0;
} else if (dp[i][j] != -1) {
return dp[i][j];
} else if ((arr[j] - arr[i]) > k) {
dp[i][j] = 1 + min(removeCombinations(arr, i + 1, j, k),
removeCombinations(arr, i, j - 1, k));
}
return dp[i][j];
}
int removeNumbers(int *arr, int n, int k){
sort(arr, arr + n);
memset(dp, -1, sizeof(dp));
return n == 1 ? 0 : removeCombinations(arr, 0, n - 1, k);
}
int main() {
int arr[] = {1, 3, 4, 9, 10, 11, 12, 17, 20};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 4;
cout << "Minimum numbers to be removed = " << removeNumbers(arr, n, k) << endl;
return 0;
}
উপরের প্রোগ্রাম কম্পাইল ও এক্সিকিউট করলে নিচের আউটপুট জেনারেট হবে
আউটপুট
Minimum numbers to be removed = 5
