Find a pair from the given array with maximum nCr value in C++

Concept

With respect of given an array arr[] of n positive integers, the task is to determineelements arr[i] and arr[j] from the array such that arr[i]Carr[j] is at most possible. With respect of more than 1 valid pairs, print any one of them.

Input 

arr[] = {4, 1, 2}

Output 

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

Method

ⁿC_r is treated as a monotonic increasing function, that is ⁿ⁺¹C_r > ⁿC_r. We can apply this fact to get close to our answer; we will select the max n among all the given integers. In this way we fixed the value of n.

Now, we concentrate for r. As we know that ⁿC_r = ⁿC_n-r , it indicates nCr will first reach its maxima and then decrease.

For odd value of n, then our maxima will occur at n / 2 and n / 2 + 1.

With respect of n = 11, we will get the maxima at ¹¹C₅ and ¹¹C₆.

For even value of n, then our maxima will occur at n / 2.

With respect of n = 4, we will get the maxima at ⁴C2

Example

 Live Demo

// 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; }

Output

6 3