Count of permutations of an Array having maximum MEXs sum of prefix arrays | 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
def factorial ( n ) : NEW_LINE INDENT res = 1 NEW_LINE for i in range ( 2 , n + 1 ) : NEW_LINE INDENT res *= i NEW_LINE DEDENT return res NEW_LINE DEDENT def countPermutations ( ar , n ) : NEW_LINE INDENT mp = dict ( ) NEW_LINE ans = 1 NEW_LINE cnt = n NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( ar [ i ] in mp ) : NEW_LINE INDENT mp [ ar [ i ] ] += 1 NEW_LINE DEDENT else : NEW_LINE INDENT mp [ ar [ i ] ] = 1 NEW_LINE DEDENT DEDENT for i in range ( n ) : NEW_LINE INDENT if ( i not in mp ) : NEW_LINE INDENT break NEW_LINE DEDENT ans = ( ans * mp [ i ] ) NEW_LINE cnt -= 1 NEW_LINE DEDENT ans = ans * factorial ( cnt ) NEW_LINE return ans NEW_LINE DEDENT arr = [ 1 , 0 , 1 ] NEW_LINE N = len ( arr ) NEW_LINE print ( countPermutations ( arr , N ) ) NEW_LINE