Encuentre el número de permutaciones que satisfacen la condición dada en una array

Dada una array arr[] de tamaño N , la tarea es encontrar el número de permutaciones en la array que sigue la condición dada: 
 

• Si K es el elemento máximo en la array, entonces los elementos antes de K en la array deben estar en orden ascendente y los elementos después de K en la array deben estar en orden descendente .

Ejemplos: 
 

Entrada: arr[] = {1, 2, 3} 
Salida: 4 
Explicación: 
Hay un total de 6 permutaciones para la array dada {1, 2, 3}. Ellos son: 
{1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2} y {3, 2, 1 } 
De las permutaciones anteriores, solo {1, 2, 3}, {1, 3, 2}, {2, 3, 1}, {3, 2, 1} son los arreglos que siguen un orden estrictamente ascendente antes del elemento máximo 3 y orden estrictamente decreciente después de él. 
Las permutaciones que no cumplen esta condición son {2, 1, 3}, {3, 1, 2}.
Entrada: arr[] = {1 1 2} 
Salida: 1 
Hay un total de 3 permutaciones para la array dada {1, 1, 2}. Ellos son: 
{1 1 2}, {1 2 1} y {2 1 1} 
De las permutaciones anteriores, solo {1, 2, 1} es la array que sigue el orden estrictamente ascendente antes del elemento máximo 2 y el orden estrictamente descendente después de él. 
Las permutaciones que no cumplen esta condición son {1, 1, 2}, {2, 2, 1}. 
 

Observaciones: Al observar detenidamente, se pueden hacer las siguientes observaciones: 
 

1. Se puede concluir que si cualquier número se repite más de dos veces, entonces no habrá permutación que satisfaga la condición dada. Esto se debe a que, en todas las permutaciones, esto se verá dos veces antes del elemento máximo o después del elemento máximo, violando así la condición dada.
2. La segunda observación que se puede hacer es que el elemento máximo de la array debe aparecer solo una vez. Si aparece más de una vez, es posible que las copias adicionales se vean antes que el elemento máximo, violando así la condición dada.

Enfoque: cuando no se violan las dos observaciones anteriores, la idea es dividir la array en dos partes y llenar los elementos en cada partición como:
 

• Ya que podemos dividir la array en dos partes. Uno está antes del elemento máximo y el otro está después del elemento máximo. Por lo tanto, cada elemento tiene dos opciones para aparecer antes del elemento máximo o después del elemento máximo excepto el elemento máximo en la array.
• Si algún elemento aparece dos veces en la array, ese elemento solo tiene una opción. Definitivamente tiene que aparecer una vez antes del elemento máximo y una vez después del elemento máximo.
• Por ejemplo, 
   

• Si arr[] = {1, 2, 2, 3, 4}, el elemento máximo 4 tiene solo una aparición y ningún elemento aparece más de dos veces.
• Ahora, la array se puede dividir en dos partes: { }4{ } siendo 4 el elemento máximo.
• Dado que 2 se repite dos veces, debería estar disponible en ambos lados (es decir, {2}4{2}).
• 1 y 3 tienen dos opciones para la parte izquierda y la parte derecha. Por lo tanto, hay 2 * 2 = 4 permutaciones posibles.

• Por lo tanto, si N es el tamaño del arreglo y M es el número de elementos en el arreglo con su ocurrencia = 2, entonces el número de permutaciones que satisfacen la condición será 2 ^{(N – (2 * X) – 1)} .

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

// C++ program to find the number
// of permutations that satisfy
// the given condition in an array
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate x ^ y
// recursively
int pow(int x, int y)
{
    if (y == 1)
        return x;
    if (y == 0)
        return 1;
 
    int temp = pow(x, y / 2);
 
    temp *= temp;
 
    if (y & 1)
        temp *= x;
 
    return temp;
}
 
// Function to return the number of
// permutations that satisfy the
// given condition in an array
int noOfPermutations(int* a, int n)
{
    // If there is only one element then
    // only one permutation is available
    if (n == 1) {
        return 1;
    }
 
    // Sort the array for calculating
    // the number of elements occurring twice
    sort(a, a + n);
 
    // If the maximum element is occurring
    // twice, then the number of permutations
    // satisfying the condition is 0
    if (a[n - 1] == a[n - 2]) {
        return 0;
    }
 
    // This variable will store the
    // number of element occurring twice
    int x = 0;
 
    // Loop to check the number of elements
    // occurring twice
    for (int i = 0; i < n - 2; ++i) {
 
        // Check if this element
        // is occurring twice
        if (a[i] == a[i + 1]) {
 
            // If this element is occurring
            // twice then check if this number
            // is occurring more than twice
            if (a[i] == a[i + 2]) {
 
                // If element occurring thrice
                // then no permutation will
                // satisfy the given condition
                return 0;
            }
 
            x++;
 
            // Since we have checked the next
            // element as well, then we can
            // increment the loop variable
            i++;
        }
    }
 
    return pow(2, n - 2 * x - 1);
}
 
// Driver code
int main()
{
    int a[] = { 1, 2, 2, 3, 4 };
    int n = sizeof(a) / sizeof(a[0]);
    int num = noOfPermutations(a, n);
    cout << num;
    return 0;
}

// Java program to find the number
// of permutations that satisfy
// the given condition in an array
 
import java.util.*;
 
class GFG{
  
// Function to calculate x ^ y
// recursively
static int pow(int x, int y)
{
    if (y == 1)
        return x;
    if (y == 0)
        return 1;
  
    int temp = pow(x, y / 2);
  
    temp *= temp;
  
    if (y % 2 == 1)
        temp *= x;
  
    return temp;
}
  
// Function to return the number of
// permutations that satisfy the
// given condition in an array
static int noOfPermutations(int []a, int n)
{
    // If there is only one element then
    // only one permutation is available
    if (n == 1) {
        return 1;
    }
  
    // Sort the array for calculating
    // the number of elements occurring twice
    Arrays.sort(a);
  
    // If the maximum element is occurring
    // twice, then the number of permutations
    // satisfying the condition is 0
    if (a[n - 1] == a[n - 2]) {
        return 0;
    }
  
    // This variable will store the
    // number of element occurring twice
    int x = 0;
  
    // Loop to check the number of elements
    // occurring twice
    for (int i = 0; i < n - 2; ++i) {
  
        // Check if this element
        // is occurring twice
        if (a[i] == a[i + 1]) {
  
            // If this element is occurring
            // twice then check if this number
            // is occurring more than twice
            if (a[i] == a[i + 2]) {
  
                // If element occurring thrice
                // then no permutation will
                // satisfy the given condition
                return 0;
            }
  
            x++;
  
            // Since we have checked the next
            // element as well, then we can
            // increment the loop variable
            i++;
        }
    }
  
    return pow(2, n - 2 * x - 1);
}
  
// Driver code
public static void main(String[] args)
{
    int a[] = { 1, 2, 2, 3, 4 };
    int n = a.length;
    int num = noOfPermutations(a, n);
    System.out.print(num);
}
}
 
// This code is contributed by 29AjayKumar

# Python 3 program to find the number
# of permutations that satisfy
# the given condition in an array
 
# Function to calculate x ^ y
# recursively
def pow( x, y):
 
    if (y == 1):
        return x
    if (y == 0):
        return 1
 
    temp = pow(x, y // 2)
 
    temp *= temp
 
    if (y & 1):
        temp *= x
 
    return temp
 
# Function to return the number of
# permutations that satisfy the
# given condition in an array
def noOfPermutations(a, n):
 
    # If there is only one element then
    # only one permutation is available
    if (n == 1):
        return 1
 
    # Sort the array for calculating
    # the number of elements occurring twice
    a.sort()
 
    # If the maximum element is occurring
    # twice, then the number of permutations
    # satisfying the condition is 0
    if (a[n - 1] == a[n - 2]):
        return 0
 
    # This variable will store the
    # number of element occurring twice
    x = 0
 
    # Loop to check the number of elements
    # occurring twice
    for i in range( n - 2):
 
        # Check if this element
        # is occurring twice
        if (a[i] == a[i + 1]):
 
            # If this element is occurring
            # twice then check if this number
            # is occurring more than twice
            if (a[i] == a[i + 2]):
 
                # If element occurring thrice
                # then no permutation will
                # satisfy the given condition
                return 0
         
            x += 1
 
            # Since we have checked the next
            # element as well, then we can
            # increment the loop variable
            i += 1
 
    return pow(2, n - 2 * x - 1)
 
# Driver code
if __name__ == "__main__":
 
    a = [ 1, 2, 2, 3, 4 ]
    n = len(a)
    num = noOfPermutations(a, n)
    print (num)
 
# This code is contributed by chitranayal

// C# program to find the number
// of permutations that satisfy
// the given condition in an array
using System;
 
class GFG{
   
// Function to calculate x ^ y
// recursively
static int pow(int x, int y)
{
    if (y == 1)
        return x;
    if (y == 0)
        return 1;
   
    int temp = pow(x, y / 2);
   
    temp *= temp;
   
    if (y % 2 == 1)
        temp *= x;
   
    return temp;
}
   
// Function to return the number of
// permutations that satisfy the
// given condition in an array
static int noOfPermutations(int []a, int n)
{
    // If there is only one element then
    // only one permutation is available
    if (n == 1) {
        return 1;
    }
   
    // Sort the array for calculating
    // the number of elements occurring twice
    Array.Sort(a);
   
    // If the maximum element is occurring
    // twice, then the number of permutations
    // satisfying the condition is 0
    if (a[n - 1] == a[n - 2]) {
        return 0;
    }
   
    // This variable will store the
    // number of element occurring twice
    int x = 0;
   
    // Loop to check the number of elements
    // occurring twice
    for (int i = 0; i < n - 2; ++i) {
   
        // Check if this element
        // is occurring twice
        if (a[i] == a[i + 1]) {
   
            // If this element is occurring
            // twice then check if this number
            // is occurring more than twice
            if (a[i] == a[i + 2]) {
   
                // If element occurring thrice
                // then no permutation will
                // satisfy the given condition
                return 0;
            }
   
            x++;
   
            // Since we have checked the next
            // element as well, then we can
            // increment the loop variable
            i++;
        }
    }
   
    return pow(2, n - 2 * x - 1);
}
   
// Driver code
public static void Main(String[] args)
{
    int []a = { 1, 2, 2, 3, 4 };
    int n = a.Length;
    int num = noOfPermutations(a, n);
    Console.Write(num);
}
}
  
// This code is contributed by 29AjayKumar

<script>
 
// JavaScript program to find the number
// of permutations that satisfy
// the given condition in an array
 
// Function to calculate x ^ y
// recursively
function pow(x, y)
{
    if (y == 1)
        return x;
    if (y == 0)
        return 1;
  
    let temp = pow(x, y / 2);
  
    temp *= temp;
  
    if (y % 2 == 1)
        temp *= x;
  
    return temp;
}
  
// Function to return the number of
// permutations that satisfy the
// given condition in an array
function noOfPermutations(a, n)
{
    // If there is only one element then
    // only one permutation is available
    if (n == 1) {
        return 1;
    }
  
    // Sort the array for calculating
    // the number of elements occurring twice
    a.sort();
  
    // If the maximum element is occurring
    // twice, then the number of permutations
    // satisfying the condition is 0
    if (a[n - 1] == a[n - 2]) {
        return 0;
    }
  
    // This variable will store the
    // number of element occurring twice
    let x = 0;
  
    // Loop to check the number of elements
    // occurring twice
    for (let i = 0; i < n - 2; ++i) {
  
        // Check if this element
        // is occurring twice
        if (a[i] == a[i + 1]) {
  
            // If this element is occurring
            // twice then check if this number
            // is occurring more than twice
            if (a[i] == a[i + 2]) {
  
                // If element occurring thrice
                // then no permutation will
                // satisfy the given condition
                return 0;
            }
  
            x++;
  
            // Since we have checked the next
            // element as well, then we can
            // increment the loop variable
            i++;
        }
    }
  
    return pow(2, n - 2 * x - 1);
}
 
// Driver code
 
    let a = [ 1, 2, 2, 3, 4 ];
    let n = a.length;
    let num = noOfPermutations(a, n);
    document.write(num);
 
</script>

4

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

Espacio Auxiliar: O(log y)