C++ में अधिकतम nCr मान के साथ दिए गए सरणी से एक जोड़ी खोजें

अवधारणा

एन सकारात्मक पूर्णांक के एक सरणी गिरफ्तारी [] दिए जाने के संबंध में, कार्य सरणी से गिरफ्तार [i] और गिरफ्तारी [जे] तत्वों को निर्धारित करना है जैसे कि गिरफ्तारी [i] कैर [जे] सबसे अधिक संभव है। 1 से अधिक मान्य जोड़े के संबंध में, उनमें से किसी एक को प्रिंट करें।

इनपुट

arr[] = {4, 1, 2}

आउटपुट

4 2
4C1 = 4
4C2 = 4
2C1 = 4
(4, 2) is the only pairs with maximum nCr.

विधि

ⁿ सी<उप>आर एक मोनोटोनिक बढ़ते कार्य के रूप में माना जाता है, जो कि ⁿ⁺¹ . है सी<उप>आर> ⁿ सी<उप>आर . हम इस तथ्य को अपने उत्तर के करीब लाने के लिए लागू कर सकते हैं; हम दिए गए सभी पूर्णांकों में से अधिकतम n का चयन करेंगे। इस तरह हमने n का मान निर्धारित किया।

अब, हम r के लिए ध्यान केंद्रित करते हैं। जैसा कि हम जानते हैं कि ⁿ सी<उप>आर = ⁿ सी<उप>एन-आर , यह इंगित करता है कि nCr पहले अपनी अधिकतम सीमा तक पहुंचेगा और फिर घटेगा।

n के विषम मान के लिए, हमारा अधिकतम मान n/2 और n/2 + 1 पर होगा।

n =11 के संबंध में, हम ¹¹ . पर उच्चिष्ठ प्राप्त करेंगे सी<उप>5 और ¹¹ सी<उप>6 ।

n के सम मान के लिए, तब हमारा उच्चिष्ठ n / 2 पर होगा।

n =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