Count the number of subsequences of length k having equal LCM and HCF | C ++ implementation ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; long long fact ( int n ) { long long res = 1 ; for ( int i = 2 ; i <= n ; i ++ ) res = res * i ; return res ; } long long nCr ( int n , int r ) { return fact ( n ) / ( 1LL * fact ( r ) * fact ( n - r ) ) ; } long long number_of_subsequences ( int arr [ ] , int k , int n ) { long long s = 0 ; map < int , int > m ; for ( int i = 0 ; i < n ; i ++ ) { m [ arr [ i ] ] ++ ; } for ( auto j : m ) { s = s + 1LL * nCr ( j . second , k ) ; } return s ; } int main ( ) { int arr [ ] = { 1 , 1 , 1 , 1 , 2 , 2 , 2 } ; int k = 2 ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << number_of_subsequences ( arr , k , n ) ; return 0 ; }