Count of permutations of an Array having maximum MEXs sum of prefix arrays | C ++ program for the above approach ; To calculate the factorial ; To return the number of permutations of an array with maximum MEXs sum of prefix array ; Map to store the frequency of each element ; Running a loop from i = 0 to i < n ; If continuity breaks , then break the loop ; Considering choices available to be filled at this position , i . e . mp [ i ] ; Decrement the count of remaining right elements ; Adding all permutations of the elements present to the right of the point where continuity breaks . ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int factorial ( int n ) { int res = 1 , i ; for ( i = 2 ; i <= n ; i ++ ) { res *= i ; } return res ; } int countPermutations ( int ar [ ] , int n ) { unordered_map < int , int > mp ; int ans = 1 , cnt = n ; for ( int i = 0 ; i < n ; i ++ ) { mp [ ar [ i ] ] ++ ; } for ( int i = 0 ; i < n ; i ++ ) { if ( mp [ i ] == 0 ) { break ; } ans = ( ans * mp [ i ] ) ; cnt -- ; } ans = ans * factorial ( cnt ) ; return ans ; } int main ( ) { int arr [ ] = { 1 , 0 , 1 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << countPermutations ( arr , N ) ; }