Count the number of subsequences of length k having equal LCM and HCF | 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
def fact ( n ) : NEW_LINE INDENT res = 1 NEW_LINE for i in range ( 2 , n + 1 ) : NEW_LINE INDENT res = res * i NEW_LINE DEDENT return res NEW_LINE DEDENT def nCr ( n , r ) : NEW_LINE INDENT return fact ( n ) // ( fact ( r ) * fact ( n - r ) ) NEW_LINE DEDENT def number_of_subsequences ( arr , k , n ) : NEW_LINE INDENT s = 0 NEW_LINE m = dict ( ) NEW_LINE for i in arr : NEW_LINE INDENT m [ i ] = m . get ( i , 0 ) + 1 NEW_LINE DEDENT for j in m : NEW_LINE INDENT s = s + nCr ( m [ j ] , k ) NEW_LINE DEDENT return s NEW_LINE DEDENT arr = [ 1 , 1 , 1 , 1 , 2 , 2 , 2 ] NEW_LINE k = 2 NEW_LINE n = len ( arr ) NEW_LINE print ( number_of_subsequences ( arr , k , n ) ) NEW_LINE