ধারণা
n ধনাত্মক পূর্ণসংখ্যার একটি অ্যারে অ্যারে [] দেওয়া হলে, কাজটি হল অ্যারে থেকে অ্যারে[i] এবং অ্যার[j] উপাদানগুলি নির্ধারণ করা যাতে arr[i]Carr[j] সর্বাধিক সম্ভব। 1 টিরও বেশি বৈধ জোড়ার ক্ষেত্রে, তাদের যেকোনো একটি প্রিন্ট করুন।
ইনপুট
arr[] = {4, 1, 2} আউটপুট
4 2 4C1 = 4 4C2 = 4 2C1 = 4 (4, 2) is the only pairs with maximum nCr.
পদ্ধতি
n Cr একটি একঘেয়ে ক্রমবর্ধমান ফাংশন হিসাবে বিবেচনা করা হয়, যেটি হল n+1 Cr> n Cr . আমরা আমাদের উত্তরের কাছাকাছি যেতে এই সত্যটি প্রয়োগ করতে পারি; আমরা প্রদত্ত সমস্ত পূর্ণসংখ্যার মধ্যে সর্বাধিক n নির্বাচন করব। এইভাবে আমরা n এর মান ঠিক করেছি।
এখন, আমরা r জন্য মনোনিবেশ. আমরা জানি যে n Cr = n Cn-r , এটি নির্দেশ করে যে nCr প্রথমে তার সর্বোচ্চ সীমায় পৌঁছাবে এবং তারপর হ্রাস পাবে৷
৷n এর বিজোড় মানের জন্য, তাহলে আমাদের ম্যাক্সিমা হবে n / 2 এবং n / 2 + 1 এ।
n =11 এর ক্ষেত্রে, আমরা 11 এ ম্যাক্সিমা পাব C5 এবং 11 C6 .
n এর জোড় মানের জন্য, তাহলে আমাদের ম্যাক্সিমা হবে n/2 এ।
n =4 এর সাপেক্ষে, আমরা 4 এ ম্যাক্সিমা পাব C2
উদাহরণ
// This is C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Now Function to print the pair that gives maximum nCr
void printMaxValPair1(vector<long long>& v1, int n1){
sort(v1.begin(), v1.end());
// This provides the value of N in nCr
long long N1 = v1[n1 - 1];
// Case 1 : When N1 is odd
if (N1 % 2 == 1) {
long long first_maxima1 = N1 / 2;
long long second_maxima1 = first_maxima1 + 1;
long long ans1 = 3e18, ans2 = 3e18;
long long from_left1 = -1, from_right1 = -1;
long long from = -1;
for (long long i = 0; i < n1; ++i) {
if (v1[i] > first_maxima1) {
from = i;
break;
}
else {
long long diff = first_maxima1 - v1[i];
if (diff < ans1) {
ans1 = diff;
from_left1 = v1[i];
}
}
}
from_right1 = v1[from];
long long diff1 = first_maxima1 - from_left1;
long long diff2 = from_right1 - second_maxima1;
if (diff1 < diff2)
cout << N1 << " " << from_left1;
else
cout << N1 << " " << from_right1;
}
// Case 2 : When N1 is even
else {
long long maxima = N1 / 2;
long long ans1 = 3e18;
long long R = -1;
for (long long i = 0; i < n1 - 1; ++i) {
long long diff = abs(v1[i] - maxima);
if (diff < ans1) {
ans1 = diff;
R = v1[i];
}
}
cout << N1 << " " << R;
}
}
// Driver code
int main(){
vector<long long> v1 = { 1, 1, 2, 3, 6, 1 };
int n1 = v1.size();
printMaxValPair1(v1, n1);
return 0;
} আউটপুট
6 3
