Find the Number of Maximum Product Quadruples | CPP program to find the number of Quadruples having maximum product ; Returns the number of ways to select r objects out of available n choices ; ncr = ( n * ( n - 1 ) * ( n - 2 ) * ... . . ... ( n - r + 1 ) ) / ( r * ( r - 1 ) * ... * 1 ) ; Returns the number of quadruples having maximum product ; stores the frequency of each element ; remaining_choices denotes the remaining elements to select inorder to form quadruple ; traverse the elements of the map in reverse order ; If Frequency of element < remaining choices , select all of these elements , else select only the number of elements required ; Decrement remaining_choices acc to the number of the current elements selected ; if the quadruple is formed stop the algorithm ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int NCR ( int n , int r ) { int numerator = 1 ; int denominator = 1 ; while ( r > 0 ) { numerator *= n ; denominator *= r ; n -- ; r -- ; } return ( numerator / denominator ) ; } int findWays ( int arr [ ] , int n ) { map < int , int > count ; if ( n < 4 ) return 0 ; for ( int i = 0 ; i < n ; i ++ ) { count [ arr [ i ] ] ++ ; } int remaining_choices = 4 ; int ans = 1 ; for ( auto iter = count . rbegin ( ) ; iter != count . rend ( ) ; ++ iter ) { int number = iter -> first ; int frequency = iter -> second ; int toSelect = min ( remaining_choices , frequency ) ; ans = ans * NCR ( frequency , toSelect ) ; remaining_choices -= toSelect ; if ( ! remaining_choices ) { break ; } } return ans ; } int main ( ) { int arr [ ] = { 1 , 2 , 3 , 3 , 3 , 5 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int maxQuadrupleWays = findWays ( arr , n ) ; cout << maxQuadrupleWays ; return 0 ; }