Number of possible permutations when absolute difference between number of elements to the right and left are given | C ++ implementation of the above approach ; Function to find the number of permutations possible of the original array to satisfy the given absolute differences ; To store the count of each a [ i ] in a map ; if n is odd ; check the count of each whether it satisfy the given criteria or not ; there is only 1 way for middle element . ; for others there are 2 ways . ; now find total ways ; When n is even . ; there will be no middle element so for each a [ i ] there will be 2 ways ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int totalways ( int * arr , int n ) { unordered_map < int , int > cnt ; for ( int i = 0 ; i < n ; ++ i ) { cnt [ arr [ i ] ] ++ ; } if ( n % 2 == 1 ) { int start = 0 , endd = n - 1 ; for ( int i = start ; i <= endd ; i = i + 2 ) { if ( i == 0 ) { if ( cnt [ i ] != 1 ) { return 0 ; } } else { if ( cnt [ i ] != 2 ) { return 0 ; } } } int ways = 1 ; start = 2 , endd = n - 1 ; for ( int i = start ; i <= endd ; i = i + 2 ) { ways = ways * 2 ; } return ways ; } else if ( n % 2 == 0 ) { int start = 1 , endd = n - 1 ; for ( int i = 1 ; i <= endd ; i = i + 2 ) { if ( cnt [ i ] != 2 ) return 0 ; } int ways = 1 ; for ( int i = start ; i <= endd ; i = i + 2 ) { ways = ways * 2 ; } return ways ; } } int main ( ) { int N = 5 ; int arr [ N ] = { 2 , 4 , 4 , 0 , 2 } ; cout << totalways ( arr , N ) ; return 0 ; }