Count the number of subsequences of length k having equal LCM and HCF | Java implementation for above approach ; Returns factorial of n ; Returns nCr for the given values of r and n ; Map to store the frequencies of each elements ; Loop to store the frequencies of elements in the map ; Using nCR formula to calculate the number of subsequences of a given length ; Driver Code ; Function calling
import java . util . * ; class GFG { static long fact ( int n ) { long res = 1 ; for ( int i = 2 ; i <= n ; i ++ ) res = res * i ; return res ; } static long nCr ( int n , int r ) { return fact ( n ) / ( 1 * fact ( r ) * fact ( n - r ) ) ; } static long number_of_subsequences ( int arr [ ] , int k , int n ) { long s = 0 ; HashMap < Integer , Integer > mp = new HashMap < Integer , Integer > ( ) ; for ( int i = 0 ; i < n ; i ++ ) { if ( mp . containsKey ( arr [ i ] ) ) { mp . put ( arr [ i ] , mp . get ( arr [ i ] ) + 1 ) ; } else { mp . put ( arr [ i ] , 1 ) ; } } for ( Map . Entry < Integer , Integer > j : mp . entrySet ( ) ) { s = s + 1 * nCr ( j . getValue ( ) , k ) ; } return s ; } static public void main ( String [ ] arg ) { int arr [ ] = { 1 , 1 , 1 , 1 , 2 , 2 , 2 } ; int k = 2 ; int n = arr . length ; System . out . println ( number_of_subsequences ( arr , k , n ) ) ; } }