Count of possible arrays from prefix | C ++ implementation of the above approach ; Function to find power of a number . ; Function to find factorial of a number . ; Function to print no of arrays ; c variable counts the no of pairs ; Map to store the frequency of each element ; Sum of all elements of the array ; Variable to check if it is possible to make any array ; First element of suffix array and the last element of prefix array ; Check if the element exists in the map ; If elements of any pair are equal and their frequency is not divisible by 2 update the isArrayPossible variable to false and break through the loop ; If elements of any pair are not equal and their frequency is not same update the isArrayPossible variable to false and break through the loop ; Check if frequency is greater than zero ; update the count of pairs ; Multiply the answer by 2 ^ ( frequency of pairs ) since the elements of the pair are not the same in this condition ; Divide the answer by the factorial of no of similar pairs ; Make frequency of both these elements 0 ; Update the count of pairs ; Divide the answer by the factorial of no . of similar pairs ; Make frequency of this element 0 ; Check if it is possible to make the array and there are n - 1 pairs whose sum will be equal to s1 ; Driver code ; Function calling
#include <bits/stdc++.h> NEW_LINE using namespace std ; int power ( int a , int b ) { int result = 1 ; while ( b > 0 ) { if ( b % 2 == 1 ) { result = result * a ; } a = a * a ; b = b / 2 ; } return result ; } int factorial ( int n ) { int fact = 1 ; for ( int i = 1 ; i <= n ; i ++ ) { fact = fact * i ; } return fact ; } void findNoOfArrays ( int * a , int n ) { int sum = 0 , s1 , c = 0 ; map < int , int > mp ; for ( int i = 0 ; i < 2 * n ; i ++ ) { mp [ a [ i ] ] ++ ; sum = sum + a [ i ] ; } bool isArrayPossible = true ; int ans = factorial ( n - 1 ) ; s1 = sum / ( n + 1 ) ; if ( mp [ s1 ] >= 2 ) { mp [ s1 ] = mp [ s1 ] - 2 ; } else { isArrayPossible = false ; } if ( isArrayPossible ) { for ( auto i : mp ) { if ( i . first == s1 - i . first ) { if ( mp [ i . first ] % 2 != 0 ) { isArrayPossible = false ; break ; } } if ( i . first != s1 - i . first ) { if ( mp [ i . first ] != mp [ s1 - i . first ] ) { isArrayPossible = false ; break ; } } if ( i . second > 0 ) { if ( i . first != s1 - i . first ) { c = c + i . second ; ans = ans * power ( 2 , i . second ) ; ans = ans / factorial ( i . second ) ; mp [ i . first ] = 0 ; mp [ s1 - i . first ] = 0 ; } if ( i . first == s1 - i . first ) { c = c + i . second / 2 ; ans = ans / factorial ( i . second / 2 ) ; mp [ i . first ] = 0 ; } } } } if ( c < n - 1 isArrayPossible == false ) { cout << "0" << endl ; } else { cout << ans << endl ; } } int main ( ) { int arr1 [ ] = { 5 , 2 , 3 , 5 } ; int n1 = sizeof ( arr1 ) / sizeof ( arr1 [ 0 ] ) ; findNoOfArrays ( arr1 , n1 / 2 ) ; int arr2 [ ] = { -1 , -1 , -1 , 0 , 1 , 0 , 1 , 0 , 1 , 0 , 0 , 0 } ; int n2 = sizeof ( arr2 ) / sizeof ( arr2 [ 0 ] ) ; findNoOfArrays ( arr2 , n2 / 2 ) ; return 0 ; }