Find the Number of Maximum Product Quadruples | Java 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 ; Getting an iterator ; 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
import java . util . * ; class Solution { static int NCR ( int n , int r ) { int numerator = 1 ; int denominator = 1 ; while ( r > 0 ) { numerator *= n ; denominator *= r ; n -- ; r -- ; } return ( numerator / denominator ) ; } static int findWays ( int arr [ ] , int n ) { HashMap < Integer , Integer > count = new HashMap < Integer , Integer > ( ) ; if ( n < 4 ) return 0 ; for ( int i = 0 ; i < n ; i ++ ) { count . put ( arr [ i ] , ( count . get ( arr [ i ] ) == null ? 0 int ) count . get ( arr [ i ] ) ) ) ; } int remaining_choices = 4 ; int ans = 1 ; Iterator hmIterator = count . entrySet ( ) . iterator ( ) ; while ( hmIterator . hasNext ( ) ) { Map . Entry mapElement = ( Map . Entry ) hmIterator . next ( ) ; int number = ( int ) mapElement . getKey ( ) ; int frequency = ( int ) mapElement . getValue ( ) ; int toSelect = Math . min ( remaining_choices , frequency ) ; ans = ans * NCR ( frequency , toSelect ) ; remaining_choices -= toSelect ; if ( remaining_choices == 0 ) { break ; } } return ans ; } public static void main ( String args [ ] ) { int arr [ ] = { 1 , 2 , 3 , 3 , 3 , 5 } ; int n = arr . length ; int maxQuadrupleWays = findWays ( arr , n ) ; System . out . print ( maxQuadrupleWays ) ; } }