সমস্যা বিবৃতি
ধনাত্মক সংখ্যার একটি অ্যারে arr[] দেওয়া হলে, অ্যারেতে ন্যূনতম সংখ্যক সেট খুঁজুন যা নিম্নলিখিত সম্পত্তিকে সন্তুষ্ট করে,
- একটি সেটে সর্বোচ্চ দুটি উপাদান থাকতে পারে। দুটি উপাদান সংলগ্ন হতে হবে না।
- সেটের উপাদানগুলির যোগফল প্রদত্ত কী-এর থেকে কম বা সমান হওয়া উচিত। এটা ধরে নেওয়া যেতে পারে যে প্রদত্ত কীটি বৃহত্তম অ্যারের উপাদানের চেয়ে বড় বা সমান।
উদাহরণ
যদি arr[] ={1, 2, 3, 4} এবং k =5 হয় তাহলে নিম্নলিখিত 2 জোড়া তৈরি করা যেতে পারে −
{1, 4} এবং {2, 3}
অ্যালগরিদম
- অ্যারে সাজান
- বাছাই করা অ্যারের দুটি কোণ থেকে দুটি পয়েন্টার শুরু করুন। যদি তাদের যোগফল প্রদত্ত কী থেকে ছোট বা সমান হয়, তাহলে আমরা তাদের সেট তৈরি করি, অন্যথায় আমরা শেষ উপাদানটিকে একা বিবেচনা করি
উদাহরণ
#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
