Find a pair from the given array with maximum nCr value
Given an array arr[] of n positive integers. The task is to find elements arr[i] and arr[j] from the array such that arr[i]Carr[j] is maximum possible. In case of more than 1 valid pairs, print any one of them.
Examples:
Input: arr[] = {3, 1, 2}
Output: 3 2
3C1 = 3
3C2 = 3
2C1 = 2
(3, 1) and (3, 2) are the only pairs with maximum nCr.
Input: arr[] = {9, 2, 4, 11, 6}
Output: 11 6
Approach Name: Maximum nCr Value Pair
Steps:
- Sort the array in non-increasing order.
- Take the first two elements of the sorted array and calculate their nCr value.
- Iterate through the rest of the array and for each element, calculate its nCr value with the first element and the nCr value with the second element.
- If the nCr value with the first element is greater than the nCr value with the second element, check if the nCr value with this element is greater than the nCr value of the current maximum pair. If it is, update the maximum pair.
- If the nCr value with the second element is greater than the nCr value with the first element, check if the nCr value with this element is greater than the nCr value of the current maximum pair. If it is, update the maximum pair.
- Return the maximum pair.
C++
#include<bits/stdc++.h> using namespace std; #define ll long long ll nCr(ll n, ll r) { if (r > n - r) r = n - r; ll ans = 1; for (ll i = 1; i <= r; i++) { ans *= n - r + i; ans /= i; } return ans; } pair<ll, ll> max_nCr_value(vector<ll> arr) { sort(arr.begin(), arr.end(), greater<ll>()); pair<ll, ll> max_pair; ll max_val = INT_MIN; for ( int i = 0; i < arr.size(); i++) { for ( int j = i + 1; j < arr.size(); j++) { ll val = nCr(arr[i], arr[j]); if (val > max_val) { max_val = val; max_pair = {arr[i], arr[j]}; } } } return max_pair; } int main() { vector<ll> arr = {9, 2, 4, 11, 6}; pair<ll, ll> ans = max_nCr_value(arr); cout << ans.first << " " << ans.second << endl; return 0; } |
Java
import java.util.Arrays; public class MaxNcrValue { // Function to calculate the value of nCr (binomial coefficient) public static long nCr( int n, int r) { if (r > n - r) { r = n - r; } long ans = 1 ; for ( int i = 1 ; i <= r; i++) { ans *= n - r + i; ans /= i; } return ans; } // Function to find the pair with the maximum nCr value public static int [] maxNcrValue( int [] arr) { // Sort the array in descending order Arrays.sort(arr); reverseArray(arr); int [] maxPair = new int [ 2 ]; long maxVal = Long.MIN_VALUE; for ( int i = 0 ; i < arr.length; i++) { for ( int j = i + 1 ; j < arr.length; j++) { long val = nCr(arr[i], arr[j]); if (val > maxVal) { maxVal = val; maxPair[ 0 ] = arr[i]; maxPair[ 1 ] = arr[j]; } } } return maxPair; } // Helper function to reverse an array public static void reverseArray( int [] arr) { int left = 0 ; int right = arr.length - 1 ; while (left < right) { int temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; left++; right--; } } public static void main(String[] args) { int [] arr = { 9 , 2 , 4 , 11 , 6 }; int [] ans = maxNcrValue(arr); System.out.println(ans[ 0 ] + " " + ans[ 1 ]); } } |
Python3
import math def nCr(n, r): if r > n - r: r = n - r ans = 1 for i in range ( 1 , r + 1 ): ans * = n - r + i ans / / = i return ans def max_nCr_value(arr): arr = sorted (arr, reverse = True ) max_pair = None max_val = - math.inf for i in range ( len (arr)): for j in range (i + 1 , len (arr)): val = nCr(arr[i], arr[j]) if val > max_val: max_val = val max_pair = (arr[i], arr[j]) return max_pair arr = [ 9 , 2 , 4 , 11 , 6 ] ans = max_nCr_value(arr) print (ans[ 0 ], ans[ 1 ]) |
C#
using System; using System.Collections.Generic; class GFG { static long nCr( long n, long r) { if (r > n - r) r = n - r; long ans = 1; for ( long i = 1; i <= r; i++) { ans *= n - r + i; ans /= i; } return ans; } static Tuple< long , long > max_nCr_value(List< long > arr) { arr.Sort((a, b) => b.CompareTo(a)); // Sort the array in descending order Tuple< long , long > max_pair = new Tuple< long , long >(0, 0); long max_val = int .MinValue; for ( int i = 0; i < arr.Count; i++) { for ( int j = i + 1; j < arr.Count; j++) { long val = nCr(arr[i], arr[j]); if (val > max_val) { max_val = val; max_pair = new Tuple< long , long >(arr[i], arr[j]); } } } return max_pair; } static void Main() { List< long > arr = new List< long > { 9, 2, 4, 11, 6 }; Tuple< long , long > ans = max_nCr_value(arr); Console.WriteLine(ans.Item1 + " " + ans.Item2); } } |
Javascript
// Function to calculate nCr (binomial coefficient) using Pascal's triangle method function nCr(n, r) { // To optimize calculation, choose the smaller value between r and n-r if (r > n - r) { r = n - r; } let ans = 1; // Calculate the binomial coefficient for (let i = 1; i <= r; i++) { ans *= n - r + i; ans /= i; } return ans; } // Function to find the maximum value of nCr for any pair of elements in the array function max_nCr_value(arr) { // Sort the array in descending order arr.sort( function (a, b) { return b - a; }); let max_pair = null ; let max_val = -Infinity; // Loop through the array to find the maximum nCr value and the corresponding pair for (let i = 0; i < arr.length; i++) { for (let j = i + 1; j < arr.length; j++) { let val = nCr(arr[i], arr[j]); // Update the maximum value and the pair if a larger nCr value is found if (val > max_val) { max_val = val; max_pair = [arr[i], arr[j]]; } } } return max_pair; } // Test the function with an example array let arr = [9, 2, 4, 11, 6]; let ans = max_nCr_value(arr); // Print the results console.log( "Maximum nCr value:" , nCr(ans[0], ans[1])); console.log( "Pair:" , ans[0], ans[1]); |
11 6
the time complexity: O(n^2),
space complexity is O(1).
Approach: nCr is a monotonic increasing function, that is n + 1Cr > nCr. We can use this fact to get close to our answer, we will choose the max n among all the given integers. This way we fixed the value of n.
Now, we have to look for r. Since we know that nCr = nCn – r, it means nCr will first reach its maxima and then decrease.
If n is be odd, then our maxima will occur at n / 2 and n / 2 + 1.
For n = 11, we will get the maxima at 11C5 and 11C6.
When n is even, then our maxima will occur at n / 2.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to print the pair that gives maximum nCr void printMaxValPair(vector< long long >& v, int n) { sort(v.begin(), v.end()); // This gives the value of N in nCr long long N = v[n - 1]; // Case 1 : When N is odd if (N % 2 == 1) { long long first_maxima = N / 2; long long second_maxima = first_maxima + 1; long long ans1 = 3e18, ans2 = 3e18; long long from_left = -1, from_right = -1; long long from = -1; for ( long long i = 0; i < n; ++i) { if (v[i] > first_maxima) { from = i; break ; } else { long long diff = first_maxima - v[i]; if (diff < ans1) { ans1 = diff; from_left = v[i]; } } } from_right = v[from]; long long diff1 = first_maxima - from_left; long long diff2 = from_right - second_maxima; if (diff1 < diff2) cout << N << " " << from_left; else cout << N << " " << from_right; } // Case 2 : When N is even else { long long maxima = N / 2; long long ans1 = 3e18; long long R = -1; for ( long long i = 0; i < n - 1; ++i) { long long diff = abs (v[i] - maxima); if (diff < ans1) { ans1 = diff; R = v[i]; } } cout << N << " " << R; } } // Driver code int main() { vector< long long > v = { 1, 1, 2, 3, 6, 1 }; int n = v.size(); printMaxValPair(v, n); return 0; } |
Java
// Java implementation of the approach import java.util.*; class GFG { // Function to print the pair that gives maximum nCr static void printMaxValPair(Vector<Long> v, int n) { Collections.sort(v); // This gives the value of N in nCr long N = v.get(( int )n - 1 ); // Case 1 : When N is odd if (N % 2 == 1 ) { long first_maxima = N / 2 ; long second_maxima = first_maxima + 1 ; long ans1 =( long ) 3e18, ans2 = ( long )3e18; long from_left = - 1 , from_right = - 1 ; long from = - 1 ; for ( long i = 0 ; i < n; ++i) { if (v.get(( int )i) > first_maxima) { from = i; break ; } else { long diff = first_maxima - v.get(( int )i); if (diff < ans1) { ans1 = diff; from_left = v.get(( int )i); } } } from_right = v.get(( int )from); long diff1 = first_maxima - from_left; long diff2 = from_right - second_maxima; if (diff1 < diff2) System.out.println( N + " " + from_left); else System.out.println( N + " " + from_right); } // Case 2 : When N is even else { long maxima = N / 2 ; long ans1 =( int ) 3e18; long R = - 1 ; for ( long i = 0 ; i < n - 1 ; ++i) { long diff = Math.abs(v.get(( int )i) - maxima); if (diff < ans1) { ans1 = diff; R = v.get(( int )i); } } System.out.println( N + " " + R); } } // Driver code public static void main(String args[]) { long arr[] = { 1 , 1 , 2 , 3 , 6 , 1 }; Vector<Long> v = new Vector<Long>( ); for ( int i = 0 ; i < arr.length; i++) v.add(arr[i]); int n = v.size(); printMaxValPair(v, n); } } // This code is contributed by Arnab Kundu |
Python3
# Python3 implementation of the approach # Function to print the pair that # gives maximum nCr def printMaxValPair(v, n): v.sort() # This gives the value of N in nCr N = v[n - 1 ] # Case 1 : When N is odd if N % 2 = = 1 : first_maxima = N / / 2 second_maxima = first_maxima + 1 ans1, ans2 = 3 * ( 10 * * 18 ), 3 * ( 10 * * 18 ) from_left, from_right = - 1 , - 1 _from = - 1 for i in range ( 0 , n): if v[i] > first_maxima: _from = i break else : diff = first_maxima - v[i] if diff < ans1: ans1 = diff from_left = v[i] from_right = v[_from] diff1 = first_maxima - from_left diff2 = from_right - second_maxima if diff1 < diff2: print (N, from_left) else : print (N, from_right) # Case 2 : When N is even else : maxima = N / / 2 ans1 = 3 * ( 10 * * 18 ) R = - 1 for i in range ( 0 , n - 1 ): diff = abs (v[i] - maxima) if diff < ans1: ans1 = diff R = v[i] print (N, R) # Driver code if __name__ = = "__main__" : v = [ 1 , 1 , 2 , 3 , 6 , 1 ] n = len (v) printMaxValPair(v, n) # This code is contributed by # Rituraj Jain |
C#
// C# implementation of the approach using System; using System.Collections.Generic; class GFG { // Function to print the pair that gives maximum nCr static void printMaxValPair(List< long > v, int n) { v.Sort(); // This gives the value of N in nCr long N = v[( int )n - 1]; // Case 1 : When N is odd if (N % 2 == 1) { long first_maxima = N / 2; long second_maxima = first_maxima + 1; long ans1 = ( long ) 3e18, ans2 = ( long )3e18; long from_left = -1, from_right = -1; long from = -1; for ( long i = 0; i < n; ++i) { if (v[( int )i] > first_maxima) { from = i; break ; } else { long diff = first_maxima - v[( int )i]; if (diff < ans1) { ans1 = diff; from_left = v[( int )i]; } } } from_right = v[( int ) from ]; long diff1 = first_maxima - from_left; long diff2 = from_right - second_maxima; if (diff1 < diff2) Console.WriteLine( N + " " + from_left); else Console.WriteLine( N + " " + from_right); } // Case 2 : When N is even else { long maxima = N / 2; long ans1 = ( long )3e18; long R = -1; for ( long i = 0; i < n - 1; ++i) { long diff = Math.Abs(v[( int )i] - maxima); if (diff < ans1) { ans1 = diff; R = v[( int )i]; } } Console.WriteLine( N + " " + R); } } // Driver code public static void Main(String []args) { long []arr = { 1, 1, 2, 3, 6, 1}; List< long > v = new List< long >( ); for ( int i = 0; i < arr.Length; i++) v.Add(arr[i]); int n = v.Count; printMaxValPair(v, n); } } // This code contributed by Rajput-Ji |
Javascript
<script> // Javascript implementation of the approach // Function to print the pair that gives maximum nCr function printMaxValPair(v, n) { v.sort((a,b)=>a-b) // This gives the value of N in nCr var N = v[n - 1]; // Case 1 : When N is odd if (N % 2 == 1) { var first_maxima = N / 2; var second_maxima = first_maxima + 1; var ans1 = 3000000000000000000, ans2 = 3000000000000000000; var from_left = -1, from_right = -1; var from = -1; for ( var i = 0; i < n; ++i) { if (v[i] > first_maxima) { from = i; break ; } else { var diff = first_maxima - v[i]; if (diff < ans1) { ans1 = diff; from_left = v[i]; } } } from_right = v[from]; var diff1 = first_maxima - from_left; var diff2 = from_right - second_maxima; if (diff1 < diff2) document.write( N + " " + from_left); else document.write( N + " " + from_right); } // Case 2 : When N is even else { var maxima = parseInt(N / 2); var ans1 = 3000000000000000000; var R = -1; for ( var i = 0; i < n - 1; ++i) { var diff = Math.abs(v[i] - maxima); if (diff < ans1) { ans1 = diff; R = v[i]; } } document.write( N + " " + R); } } // Driver code var v = [1, 1, 2, 3, 6, 1 ]; var n = v.length; printMaxValPair(v, n); // This code is contributed by famously. </script> |
PHP
<?php // PHP implementation of the approach // Function to print the pair that // gives maximum nCr function printMaxValPair( $v , $n ) { sort( $v ); // This gives the value of N in nCr $N = $v [ $n - 1]; // Case 1 : When N is odd if ( $N % 2 == 1) { $first_maxima = $N / 2; $second_maxima = $first_maxima + 1; $ans1 = 3e18; $ans2 = 3e18; $from_left = -1; $from_right = -1; $from = -1; for ( $i = 0; $i < $n ; ++ $i ) { if ( $v [ $i ] > $first_maxima ) { $from = $i ; break ; } else { $diff = $first_maxima - $v [ $i ]; if ( $diff < $ans1 ) { $ans1 = $diff ; $from_left = $v [ $i ]; } } } $from_right = $v [ $from ]; $diff1 = $first_maxima - $from_left ; $diff2 = $from_right - $second_maxima ; if ( $diff1 < $diff2 ) echo $N . " " . $from_left ; else echo $N . " " . $from_right ; } // Case 2 : When N is even else { $maxima = $N / 2; $ans1 = 3e18; $R = -1; for ( $i = 0; $i < $n - 1; ++ $i ) { $diff = abs ( $v [ $i ] - $maxima ); if ( $diff < $ans1 ) { $ans1 = $diff ; $R = $v [ $i ]; } } echo $N . " " . $R ; } } // Driver code $v = array ( 1, 1, 2, 3, 6, 1 ); $n = count ( $v ); printMaxValPair( $v , $n ); // This code is contributed by mits ?> |
6 3
Time Complexity: O(n * log n)
Auxiliary Space: O(1)
Contact Us