C++ में दिए गए सरणी से एक युग्म खोजें जिसका nCr मान अधिकतम हो

अवधारणा

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

उदाहरण

इनपुट

arr[] = {4, 1, 2}

आउटपुट

4 2
4C1 = 4, 4C2 = 6, 2C1 = 2 (4, 2) अधिकतम nCr वाला एकमात्र युग्म है।

विधि

nCr एक मोनोटोनिक बढ़ता हुआ फलन है, अर्थात n+1Cr > nCr। हम इस तथ्य का उपयोग अपने उत्तर के करीब पहुंचने के लिए कर सकते हैं; हम दिए गए सभी पूर्णांकों में से अधिकतम n का चयन करेंगे। इस तरह हम n का मान तय करते हैं।

अब, हम r पर ध्यान केंद्रित करते हैं। जैसा कि हम जानते हैं कि nCr = nC(n-r), यह दर्शाता है कि nCr पहले अपने अधिकतम पर पहुंचेगा और फिर घटेगा।

• n के विषम मान के लिए, हमारा अधिकतम n/2 और n/2 + 1 पर होगा। n = 11 के लिए, हमें अधिकतम 11C5 और 11C6 पर मिलेगा।
• n के सम मान के लिए, हमारा अधिकतम n/2 पर होगा। n = 4 के लिए, हमें अधिकतम 4C2 पर मिलेगा।

C++ कार्यान्वयन

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;

void printMaxValPair1(vector<long long>& v1, int n1){
    sort(v1.begin(), v1.end());
    long long N1 = v1[n1 - 1];
    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;
    }
    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;
    }
}

int main(){
    vector<long long> v1 = { 1, 1, 2, 3, 6, 1 };
    int n1 = v1.size();
    printMaxValPair1(v1, n1);
    return 0;
}

आउटपुट

6 3