Número de formas de seleccionar K número par pequeño desde la izquierda de cada elemento en una array dada

array , arr[] N selecciona K elementos.

Entrada: arr[] = {4, 2, 12, 33}, K = 2
Salida: 0 0 1 3
Explicación: 

1. Para arr[0](=4), hay 0, incluso elementos menores que arr[i]. Por lo tanto, las formas de seleccionar 2 elementos de 0 elementos son iguales a C(0, 2) = 0.
2. Para arr[1](=2), hay 0, incluso elementos menores que arr[i]. Por lo tanto, las formas de seleccionar 2 elementos de 0 elementos son iguales a C(0, 2) = 0.
3. Para arr[2](=12), hay 2 elementos pares menores que arr[i]. Por lo tanto, las formas de seleccionar 2 elementos de 2 elementos es igual a C(2, 2) es 1.
4. Para arr[3](=33), hay 3 elementos pares menores que arr[i]. Por lo tanto, las formas de seleccionar 2 elementos de 3 elementos es igual a C(3, 2) es 3.
    

Entrada: arr[] = {1, 2, 3}, K = 2
Salida: 0 0 1 

Enfoque ingenuo: el enfoque más simple es atravesar la array y para cada elemento encontrar todos los números que son más pequeños que el elemento dado e, incluso en el lado izquierdo, y verificar si el conteo es menor que K, luego imprimir   0 , De lo contrario, Usa la combinatoria para encontrar el número de formas.

Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(1) 

Enfoque eficiente: el enfoque anterior se puede optimizar mediante el uso de una estructura de datos de conjuntos ordenados . Siga los pasos a continuación para resolver el problema:

• Inicialice un conjunto ordenado , diga S para almacenar los valores que son pares.
• Además, inicialice una array, digamos ans[], para almacenar los resultados.
• Recorra el arreglo , arr[] usando la variable i y realice los siguientes pasos:
  • Si el tamaño del conjunto S es 0 , entonces asigne 0 a ans[i] y continúe .
  • Encuentre el recuento de elementos menores que arr[i] usando la función order_of_key() en el conjunto S y guárdelo en una variable, por ejemplo, count .
  • Ahora asigne el conteo de formas de seleccionar K elementos del conteo i, e C(contar, K) al ans[i].
• Finalmente, después de completar los pasos anteriores, imprima la array ans[i].

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
  
// Policy based data structure
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
  
#define ordered_set                              \
    tree<int, null_type, less<int>, rb_tree_tag, \
         tree_order_statistics_node_update>
  
// NCR formula to find number
// of ways
int ncr(int n, int r)
{
    if (r == 0 || n == r) {
        return 1;
    }
    return ncr(n - 1, r) + ncr(n - 1, r - 1);
}
  
// Function to find the number of ways
// of selecting K smaller even element
// on the left of each element
void numberofSmallerElementsInLeft(int arr[], int N, int K)
{
    // Set to store even elements
    ordered_set S;
  
    // Stores answer for each element
    int ans[N];
  
    for (int i = 0; i < N; i++) {
        // Set is empty
        if (S.size() == 0)
            ans[i] = 0;
        else {
  
            // Finds the count of elements
            // less than arr[i]
            int count = S.order_of_key(arr[i]);
  
            // If count is 0
            if (count == 0)
                ans[i] = 0;
            // Else
            else {
  
                // Number of ways to choose k
                // elements from pos
                ans[i] = ncr(count, K);
            }
        }
  
        // If the element is even
        // insert it into S
        if (arr[i] % 2 == 0)
            S.insert(arr[i]);
    }
    // Print the result
    for (int i = 0; i < N; i++) {
        cout << ans[i] << " ";
    }
}
  
// Driver Code
int main()
{
  
    // Input
    int arr[] = { 4, 2, 12, 33 };
    int K = 2;
    int N = sizeof(arr) / sizeof(arr[0]);
  
    // Function Call
    numberofSmallerElementsInLeft(arr, N, K);
    return 0;
}

0 0 1 3 

Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(N)