Formas de formar n/2 pares de manera que la diferencia de pares sea mínima

Dada una array arr de N enteros, la tarea es dividir los elementos de la array en N/2 pares (cada par tiene 2 elementos) de modo que la diferencia absoluta entre dos elementos de cualquier par sea la mínima posible. Nota: N siempre será par. Ejemplos:

Entrada: arr[] = {1, 7, 3, 8} Salida: 1 Solo hay una forma de formar pares con diferencia mínima, (7, 8) y (1, 3). Entrada: arr[] = {1, 1, 1, 1, 2, 2, 2, 2} Salida: 9 Aquí todos los elementos con valor 2 se emparejarán entre sí (3 formas posibles) y todos los elementos con valor 1 formarán pares entre ellos (3 formas posibles) Por lo tanto, número de formas = 3 * 3 = 9 Entrada: arr[] = {2, 3, 2, 2} Salida: 3

Enfoque: Este problema implica el principio fundamental de contar y cierta comprensión básica de permutaciones y combinaciones. Antes de continuar, contemos el número de formas para el arreglo = [3, 3] Respuesta = 1, ya que solo es posible 1 combinación. Ahora, modifiquemos la array a [3, 3, 3, 3]. Las formas para esto, como se discutió en los ejemplos anteriores, son:

(1, 2), (3, 4) (1, 3), (2, 4) (1, 4), (2, 3) Respuesta = 3 formas.

Modificando aún más la array a [3, 3, 3, 3, 3, 3]

(1, 2), (3, 4), (5, 6) (1, 2), (3, 5), (4, 6) (1, 2), (3, 6), (4, 5) ) (1, 3), (2, 4), (5, 6) (1, 3), (2, 5), (4, 6) (1, 3), (2, 6), (4, 5) (1, 4), (2, 3), (5, 6) (1, 4), (2, 5), (3, 6) (1, 4), (2, 6), (3 , 5) (1, 5), (2, 3), (4, 6) (1, 5), (2, 4), (3, 6) (1, 5), (2, 6), ( 3, 4) (1, 6), (2, 3), (4, 5) (1, 6), (2, 4), (3, 5) (1, 6), (2, 5), (3, 4) Respuesta = 15 maneras.

Aquí obtenemos un resultado generalizado por simple observación. Si hay K elementos en la array que tienen el mismo valor y K es par , entonces el número de formas de formar pares entre ellos:

Para el tamaño 2, cuenta = 1 (1) Para el tamaño 4, cuenta = 3 (1 * 3) Para el tamaño 6, cuenta = 15 (1 * 3 * 5) Y así sucesivamente. Por lo tanto, número de formas de formar pares para el tamaño K donde K es par = 1 * 3 * 5 * …. * (K-1)

Podemos precalcular este resultado de la siguiente manera. Deje queways[] sea la array tal queways[i] almacene el número de formas para el tamaño ‘i’.

caminos[2] = 1; for(i = 4; i < 1e5 + 1; i += 2) vías[i] = vías[i – 2] * (i – 1); Por ejemplo, consideramos la array [3, 3, 3, 3, 3] Para calcular el número de formas, fijamos el primer elemento con cualquiera de los 5 restantes. Entonces formamos un par. Ahora quedan 4 elementos que se pueden emparejar de formas[4] formas. Entonces, el número de formas sería 5 * formas [4] .

Ahora bien, puede que no sea necesario que los recuentos sean siempre pares en número. Por lo tanto, si necesitamos resolver esto para una array general, debemos hacer dos cosas.

1. Ordene la array en orden ascendente.
2. Analice el recuento de cada grupo que tiene el mismo valor.

Sea nuestra array = [2, 3, 3, 3, 3, 4, 4, 4, 4, 4] . Esta array está ordenada.

• Considerando elemento con valor 4. Como hay 5 elementos, 4 elementos se emparejarán entre sí de maneras[4] formas. El elemento omitido se puede elegir de 5 maneras. El elemento que quede tendrá que emparejarse con un elemento de valor 3. Esto sucede de 4 formas ya que hay 4 elementos con valor 3. Por lo tanto, un elemento de valor 3 se reservará para emparejarse con un elemento de 4. Entonces 3 elementos con valor el valor 3 permanece. 2 se emparejarán entre sí en formas[2] formas y un 1 se emparejará con el elemento con valor 2 en 1 forma. Nuevamente, el elemento solitario se seleccionará de 3 maneras.
• Por tanto, a partir del punto 1, el número de vías será:

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

// C++ implementation of the above approach
#include <bits/stdc++.h>
 
#define mp make_pair
#define pb push_back
#define S second
#define ll long long
 
using namespace std;
 
// Using mod because the number
// of ways might be very large
const int mod = 1000000007;
 
const int MAX = 100000;
 
// ways is serving the same
// purpose as discussed
ll ways[MAX + 1];
 
void preCompute()
{
    // pairing up zero people
    // requires one way.
    ways[0] = 1LL;
    ways[2] = 1LL;
    for (int i = 4; i <= MAX; i += 2) {
        ways[i] = (1LL * (i - 1) * ways[i - 2]) % mod;
    }
}
 
void countWays(int* arr, int n)
{
 
    // map count stores count of s.
    map<int, int> count;
    for (int i = 0; i < n; i++)
        count[arr[i]]++;
 
    vector<pair<int, int> > count_vector;
    map<int, int>::iterator it;
    for (it = count.begin(); it != count.end(); it++) {
        count_vector.pb(mp(it->first, it->second));
    }
 
    // vector count_vector stores a
    // pair < value, count of value>
 
    // sort according to value
    sort(count_vector.begin(), count_vector.end());
 
    ll ans = 1;
 
    // Iterating backwards.
    for (int i = count_vector.size() - 1; i > 0; i--) {
 
        int current_count = count_vector[i].S;
        int prev_count = count_vector[i - 1].S;
 
        // Checking if current count is odd.
        if (current_count & 1) {
 
            // if current count = 5, multiply ans by ways[4].
            ans = (ans * ways[current_count - 1]) % mod;
 
            // left out person will be selected
            // in current_count ways
            ans = (ans * current_count) % mod;
 
            // left out person will pair with previous
            //  person in previous_count ways
            ans = (ans * prev_count) % mod;
 
            /* if previous count is odd,
             * then multiply answer by ways[prev_count-1].
             * since one has already been reserved,
             * remaining will be even.
             * reduce prev_count = 0, since we don't need it now.*/
            if (prev_count & 1) {
                ans = (ans * ways[prev_count - 1]) % mod;
                count_vector[i - 1].S = 0;
            }
            else {
 
                /* if prev count is even, one will be reserved,
                 * therefore decrement by 1.
                 * In the next iteration, prev_count will become odd
                 * and it will be handled in the same way.*/
                count_vector[i - 1].S--;
            }
        }
        else {
 
            /* if current count is even,
             * then simply multiply ways[current_count]
             * to answer.*/
            ans = (ans * ways[current_count]) % mod;
        }
    }
 
    /* multiply answer by ways[first__count] since
       that is left out, after iterating the array.*/
    ans = (ans * ways[count_vector[0].S]) % mod;
    cout << ans << "\n";
}
 
// Driver code
int main()
{
    preCompute();
    int arr[] = { 2, 3, 3, 3, 3, 4, 4, 4, 4, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    countWays(arr, n);
    return 0;
}

# Python3 implementation of the
# above approach
from collections import defaultdict
 
# Using mod because the number
# of ways might be very large
mod = 1000000007
MAX = 100000
 
# ways is serving the same
# purpose as discussed
ways = [None] * (MAX + 1)
 
def preCompute():
 
    # pairing up zero people
    # requires one way.
    ways[0] = 1
    ways[2] = 1
    for i in range(4, MAX + 1, 2):
        ways[i] = ((1 * (i - 1) *
                    ways[i - 2]) % mod)
 
def countWays(arr, n):
 
    # map count stores count of s.
    count = defaultdict(lambda:0)
    for i in range(0, n):
        count[arr[i]] += 1
 
    count_vector = []
    for key in count:
        count_vector.append([key, count[key]])
 
    # vector count_vector stores a
    # pair < value, count of value>
 
    # sort according to value
    count_vector.sort()
    ans = 1
 
    # Iterating backwards.
    for i in range(len(count_vector) - 1, -1, -1):
 
        current_count = count_vector[i][1]
        prev_count = count_vector[i - 1][1]
 
        # Checking if current count is odd.
        if current_count & 1:
 
            # if current count = 5, multiply
            # ans by ways[4].
            ans = (ans * ways[current_count - 1]) % mod
 
            # left out person will be selected
            # in current_count ways
            ans = (ans * current_count) % mod
 
            # left out person will pair with previous
            # person in previous_count ways
            ans = (ans * prev_count) % mod
 
            # if previous count is odd,
            # then multiply answer by ways[prev_count-1].
            # since one has already been reserved,
            # remaining will be even.
            # reduce prev_count = 0, since we
            # don't need it now.
            if prev_count & 1:
                ans = (ans * ways[prev_count - 1]) % mod
                count_vector[i - 1][1] = 0
             
            else:
 
                # if prev count is even, one will be
                # reserved, therefore decrement by 1.
                # In the next iteration, prev_count
                # will become odd and it will be
                # handled in the same way.
                count_vector[i - 1][1] -= 1
             
        else:
 
            # if current count is even, then simply
            # multiply ways[current_count] to answer.
            ans = (ans * ways[current_count]) % mod
         
    # multiply answer by ways[first__count] since
    # that is left out, after iterating the array.
    ans = (ans * ways[count_vector[0][1]]) % mod
    print(ans)
 
# Driver code
if __name__ == "__main__":
 
    preCompute()
    arr = [2, 3, 3, 3, 3, 4, 4, 4, 4, 4]
    n = len(arr)
    countWays(arr, n)
     
# This code is contributed by Rituraj Jain

180

Complejidad de tiempo: O (nlogn)

Espacio Auxiliar: O(MAX + n)