Count the number of subsequences of length k having equal LCM and HCF | C # 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
using System ; using System . Collections . Generic ; public 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 ; Dictionary < int , int > mp = new Dictionary < int , int > ( ) ; for ( int i = 0 ; i < n ; i ++ ) { if ( mp . ContainsKey ( arr [ i ] ) ) { var val = mp [ arr [ i ] ] ; mp . Remove ( arr [ i ] ) ; mp . Add ( arr [ i ] , val + 1 ) ; } else { mp . Add ( arr [ i ] , 1 ) ; } } foreach ( KeyValuePair < int , int > j in mp ) { s = s + 1 * nCr ( j . Value , 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 ; Console . Write ( number_of_subsequences ( arr , k , n ) ) ; } }