Recuento de tripletes de números 1 a N tales que el elemento medio es siempre el más grande

Dado un número entero N , la tarea es contar el número de formas de organizar los tripletes ( a , b , c ) dentro de [1, N] de tal manera que el elemento central siempre sea mayor que los elementos izquierdo y derecho.
 

Ejemplo:  
Entrada: N = 4 
Salida:
Explicación 
Para la entrada dada N = 4 el número de tripletes posibles es: {1, 3, 2}, {2, 3, 1}, {2, 4, 3}, {3 , 4, 2}, {1, 4, 3}, {3, 4, 1}, {2, 4, 1}, {1, 4, 2}.
Entrada: 10 
Salida: 240 
 

Enfoque ingenuo: comprueba si todos los tripletes cumplen la condición dada utilizando tres bucles anidados y continúa incrementando su conteo cada vez que un triplete satisface la condición. 
Tiempo Complejidad: O( N 3
Espacio Auxiliar: O( 1 ) 
Enfoque Eficiente: 
 

  1. Comprueba todas las posibilidades para el elemento intermedio e intenta encontrar el número de arreglos posibles manteniendo cada uno de ellos fijo uno por uno.
  2. Podemos observar que todos los números entre [3, N] pueden ocupar el espacio del medio.

Arreglos posibles para cada elemento del medio: 
Al colocar 3 en el medio, solo existen 2 (= 2 * 1) arreglos posibles {1, 3, 2} y {2, 3, 1}. 
Al colocar 4 en el medio, existen 6 (= 3 * 2) arreglos posibles {1, 4, 3}, {1, 4, 2}, {2, 4, 1}, {2, 4, 3}, { 3, 4, 1} y {3, 4, 2}. 
Al colocar 5 en el medio, existen 12 ( = 4 * 3) arreglos posibles. 



Al colocar N – 1 en el medio, (N-2) * (N-3) existen arreglos posibles. 
Al poner N en el medio, (N-1) * (N-2) existen arreglos posibles.
Así, Total arreglos posibles = ( N * (N-1) * (N-2)) / 3 
 

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

C++

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find Number of triplets
// for given Number N such that
// middle element is always greater
// than left and right side element.
int findArrangement(int N)
{
    // check if arrangement is
    // possible or Not
    if (N < 3)
        return 0;
 
    // else return total ways
    return ((N) * (N - 1) * (N - 2)) / 3;
}
 
// Driver code.
int main()
{
    int N = 10;
    cout << findArrangement(N);
    return 0;
}

Java

// Java program to implement
// the above approach
import java.io.*;
import java.util.*;
 
class GFG{
     
// Function to find number of triplets
// for given number N such that middle
// element is always greater than left 
// and right side element.
static int findArrangement(int N)
{
     
    // Check if arrangement
    // is possible or not
    if (N < 3)
        return 0;
 
    // Else return total ways
    return ((N) * (N - 1) * (N - 2)) / 3;
}
 
// Driver code
public static void main(String[] args)
{
    int N = 10;
     
    System.out.println(findArrangement(N));
}
}
 
// This code is contributed by coder001

Python3

# Python3 program to implement
# the above approach
 
# Function to find Number of triplets
# for given Number N such that middle
# element is always greater than left 
# and right side element.
def findArrangement(N):
 
    # Check if arrangement is
    # possible or Not
    if (N < 3):
        return 0;
 
    # Else return total ways
    return ((N) * (N - 1) * (N - 2)) // 3;
 
# Driver code.
N = 10;
 
print(findArrangement(N));
 
# This code is contributed by Akanksha_Rai

C#

// C# program to implement
// the above approach
using System;
class GFG{
     
// Function to find number of triplets
// for given number N such that middle
// element is always greater than left
// and right side element.
static int findArrangement(int N)
{
     
    // Check if arrangement
    // is possible or not
    if (N < 3)
        return 0;
 
    // Else return total ways
    return ((N) * (N - 1) * (N - 2)) / 3;
}
 
// Driver code
public static void Main()
{
    int N = 10;
     
    Console.Write(findArrangement(N));
}
}
 
// This code is contributed by Code_Mech

Javascript

<script>
// Javascript program to implement
// the above approach
 
// Function to find number of triplets
// for given number N such that middle
// element is always greater than left 
// and right side element.
function findArrangement(N)
{
       
    // Check if arrangement
    // is possible or not
    if (N < 3)
        return 0;
   
    // Else return total ways
    return ((N) * (N - 1) * (N - 2)) / 3;
}
  
  // Driver Code
    let N = 10;
   document.write(findArrangement(N));
 
// This code is contributed by susmitakundugoaldanga.
</script>
Producción: 

240

 

Tiempo Complejidad: O(1)  
Espacio Auxiliar: O(1)
 

Publicación traducida automáticamente

Artículo escrito por Samdare B y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *