Recuento de arrays posibles de arrays de suma de prefijo y suma de sufijo

Dados 2*N enteros que son elementos de una array de prefijos y sufijos (en orden aleatorio) de una array de tamaño N , la tarea es encontrar el número de posibles arrays de tamaño N que se pueden crear a partir de estos elementos 
Ejemplos: 
 

Entrada: arr[] = {5, 2, 3, 5} 
Salida: 2 
Explicación: 
la 1.ª array puede ser: {2, 3} 
Su array de prefijos:{2, 5} 
Su array de sufijos:{5, 3} 
2.ª array puede ser: {3, 2} 
Su array de prefijos: {3, 5} 
Su array de sufijos: {5, 2}
Entrada: arr[] = {-1, -1, -1, 0, 1, 0, 1, 0, 1, 0, 0, 0} 
Salida: 80 
 

Acercarse: 
 

• Una idea que se puede extraer es que si la suma de todos los elementos de la array dada se divide por n+1, entonces se obtiene el último y el primer elemento de una array de prefijos y sufijos, respectivamente.
• Se puede llegar a esta conclusión observando los elementos de la array de prefijos y sufijos. La suma del primer elemento de la array de prefijos y el segundo elemento de la array de sufijos es igual a la suma del segundo elemento de la array de prefijos y el tercer elemento de la array de sufijos (si hay un tercer elemento en la array de sufijos) y así sucesivamente.

• En la imagen, la primera array es la array dada, la segunda es la array de prefijos y la tercera es la array de sufijos.
• La suma de estos pares es igual a la suma de todos los elementos del arreglo a encontrar.
• Si se supone que la suma de los pares es s1 y la suma de todos los elementos de prefijo y sufijo es s entonces: 
  s1 * (n-1) + 2 * s1 = s 
  s1 = s / (n+1) 
  donde s1 es el último elemento de la array de prefijos y el primer elemento de la array de sufijos.
• Ahora, se deben encontrar todos los demás pares cuya suma sea igual a s1, lo que se puede hacer usando mapas hash.
• Si estos pares se barajan linealmente junto con la array, ¡podemos obtener la respuesta como 
  (n-1)! / (k1! * k2! … kr!) 
  donde k1, k2 … kr son el número de pares similares
• ¡ Cada par también se puede intercambiar entre sí en la array de prefijos y sufijos (si los elementos del par no son iguales), por lo que la respuesta se convierte en 
  (n-1)! * (2^p) / (k1!*k2!…kr!) 
  donde p es el número de pares distintos en el arreglo cuya suma es igual a s1.

A continuación se muestra la implementación del enfoque anterior.
 

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

// Java implementation of the above approach
import java.util.*;
 
class GFG{
     
// Function to find power of
// a number.
static 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;
}
 
// Function to find
// factorial of a number.
static int factorial(int n)
{
    int fact = 1;
    for (int i = 1; i <= n; i++) {
        fact = fact * i;
    }
    return fact;
}
 
// Function to print no of arrays
static void findNoOfArrays(int[] a, int n)
{
    // c variable counts the no of pairs
    int sum = 0, s1, c = 0;
 
    // Map to store the frequency
    // of each element
    HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>();        
 
    for (int i = 0; i < 2 * n; i++) {
        if(mp.get(a[i])==null)
          mp.put(a[i], 1);
        else
          mp.put(a[i], mp.get(a[i]) + 1);
 
        // Sum of all elements of the array
        sum = sum + a[i];
    }
 
    // Variable to check if it is
    // possible to make any array
    boolean isArrayPossible = true;
    int ans = factorial(n - 1);
 
    // First element of suffix array
    // and the last element of prefix array
    s1 = sum / (n + 1);
 
    // Check if the element exists in the map
    if (mp.get(s1) >= 2) {
        mp.replace(s1, mp.get(s1) - 2);
    }
    else {
        isArrayPossible = false;
    }
    if (isArrayPossible) {
        for (Map.Entry<Integer,Integer> m:mp.entrySet()) {
 
            // 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 (m.getKey() == s1-m.getKey()) {
                if (mp.get(m.getKey()) % 2 != 0) {
                    isArrayPossible = false;
                    break;
                }
            }
 
            // 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
 
            if (m.getKey() != s1 - m.getKey()) {
                if (mp.get(m.getKey())
                    != mp.get(s1 - m.getKey())) {
                    isArrayPossible = false;
                    break;
                }
            }
            // Check if frequency is greater than zero
            if (m.getValue() > 0) {
                if (m.getKey() != s1 - m.getKey()) {
                    // update the count of pairs
 
                    c = c + m.getValue();
 
                    // Multiply the answer by
                    // 2^(frequency of pairs) since
                    // the elements of the pair are
                    // not the same in this condition
                    ans = ans * power(2, m.getValue());
 
                    // Divide the answer by the factorial
                    // of no of similar pairs
                    ans = ans / factorial(m.getValue());
 
                    // Make frequency of both these elements 0
                    mp.replace(m.getKey(),0);
                    mp.replace(s1 - m.getKey(),0);
                }
                if (m.getKey() == s1 - m.getKey()) {
                    // Update the count of pairs
 
                    c = c + m.getValue() / 2;
 
                    // Divide the answer by the factorial
                    // of no. of similar pairs
                    ans = ans / factorial(m.getValue() / 2);
 
                    // Make frequency of this element 0
                    mp.replace(m.getKey(),0);
                }
            }
        }
    }
 
    // Check if it is possible to make the
    // array and there are n-1 pairs
    // whose sum will be equal to s1
    if (c < n - 1 && isArrayPossible == false) {
        System.out.println("0");
    }
    else {
        System.out.println(ans);
    }
}
 
// Driver code
public static void main(String args[])
{
    int[] arr1 = { 5, 2, 3, 5 };
    int n1 = arr1.length;
 
    // Function calling
    findNoOfArrays(arr1, n1 / 2);
 
    int []arr2 = { -1, -1, -1, 0, 1, 0,
                1, 0, 1, 0, 0, 0 };
    int n2 = arr2.length;
    findNoOfArrays(arr2, n2 / 2);
}
}
 
// This code is contributed by Surendra_Gangwar

# Python3 implementation of the above approach
 
# Function to find power of
# a number.
def power(a, b) :
 
    result = 1;
    while (b > 0) :
        if (b % 2 == 1) :
            result = result * a;
        a = a * a;
        b = b // 2;
     
    return result;
 
# Function to find
# factorial of a number.
def factorial(n) :
 
    fact = 1;
    for i in range(1, n + 1) :
        fact = fact * i;
     
    return fact;
 
# Function to print no of arrays
def findNoOfArrays(a, n) :
 
    # c variable counts the no of pairs
    sum = 0; c = 0;
 
    # Map to store the frequency
    # of each element
    mp = dict.fromkeys(a, 0);
 
    for i in range(2 * n) :
        mp[a[i]] += 1;
 
        # Sum of all elements of the array
        sum = sum + a[i];
 
    # Variable to check if it is
    # possible to make any array
    isArrayPossible = True;
    ans = factorial(n - 1);
 
    # First element of suffix array
    # and the last element of prefix array
    s1 = sum // (n + 1);
 
    # Check if the element exists in the map
    if (mp[s1] >= 2) :
        mp[s1] = mp[s1] - 2;
         
    else :
        isArrayPossible = False;
     
    if (isArrayPossible) :
        for first,second in mp.items() :
             
            # 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 (first == s1 - first) :
                if (mp[first] % 2 != 0) :
                    isArrayPossible = False;
                    break;
 
            # 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
            if (first != s1 - first) :
                if s1 - first in mp :
                    if (mp[first] != mp[s1 - first]) :
                        isArrayPossible = False;
                        break;
             
            # Check if frequency is greater than zero
            if (second > 0) :
                if (first != s1 - first) :
 
                    # update the count of pairs
                    c = c + second;
 
                    # Multiply the answer by
                    # 2^(frequency of pairs) since
                    # the elements of the pair are
                    # not the same in this condition
                    ans = ans * power(2, second);
 
                    # Divide the answer by the factorial
                    # of no of similar pairs
                    ans = ans / factorial(second);
 
                    # Make frequency of both these elements 0
                    mp[first] = 0;
                    mp[s1 - first] = 0;
                 
                if (first == s1 - first) :
 
                    # Update the count of pairs
                    c = c + second // 2;
 
                    # Divide the answer by the factorial
                    # of no. of similar pairs
                    ans = ans // factorial(second // 2);
 
                    # Make frequency of this element 0
                    mp[first] = 0;
 
    # Check if it is possible to make the
    # array and there are n-1 pairs
    # whose sum will be equal to s1
    if (c < n - 1 or isArrayPossible == False) :
        print("0");
    else:
        print(ans);
 
# Driver code
if __name__ == "__main__" :
 
    arr1 = [ 5, 2, 3, 5 ];
    n1 = len(arr1);
 
    # Function calling
    findNoOfArrays(arr1, n1 // 2);
 
    arr2 = [ -1, -1, -1, 0, 1, 0,
                1, 0, 1, 0, 0, 0 ];
    n2 = len(arr2);
    findNoOfArrays(arr2, n2 // 2);
     
# This code is contributed by AnkitRai01

2
80

Complejidad de tiempo: O(N Log(N))

Espacio Auxiliar: O(N)