সমস্যা বিবরণ
ধনাত্মক সংখ্যার একটি অ্যারে arr[] দেওয়া আছে, অ্যারেতে ন্যূনতম সংখ্যক সেট বের করুন যা নিচের প্রোপার্টি মেনে চলে:
- এক সেটে ম্যাক্সিমাম দুইটা এলিমেন্ট থাকতে পারে। দুটি এলিমেন্ট কন্টিগুয়াস হতে হবে না।
- সেটের এলিমেন্টগুলোর সম দिये गये Key-এর চেয়ে কম বা সমান হতে হবে। অনুমান করা হয় Key সবচেয়ে বড় অ্যারে এলিমেন্টের চেয়ে বড় বা সমান।
উদাহরণ
যদি arr[] = {1, 2, 3, 4} এবং k = 5 হয়, তবে নিচের ২টি পেয়ার তৈরি করা যায় −
{1, 4} এবং {2, 3}
অ্যালগরিদম
- অ্যারে সোর্ট করুন
- সোর্ট করা অ্যারে-এর দুটি কোণ থেকে টু পয়েন্টার শুরু করুন। যদি তাদের সম Key-এর চেয়ে কম বা সমান হয়, তবে তাদের এক সেট বানান, অন্যথায় লাস্ট এলিমেন্টকেই আলাদা কনসিডার করুন
উদাহরণ
#include <iostream>
#include <algorithm>
using namespace std;
int getMinSets(int *arr, int n, int key) {
int i, j;
sort (arr, arr + n);
for (i = 0, j = n - 1; i <= j; ++i) {
if (arr[i] + arr[j] <= key) {
--j;
}
}
return i;
}
int main() {
int arr[] = {1, 2, 3, 4};
int key = 5;
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Minimum set = " << getMinSets(arr, n, key) << endl;
return 0;
}
আউটপুট
যখন আপনি উপরের প্রোগ্রাম কম্পাইল ও এক্সিকিউট করবেন। এটি নিচের আউটপুট জেনারেট করবে:
Minimum set = 2
