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: 8
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:
- 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.
- 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>
240
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)