Dada una array arr[] de tamaño N ( 1 ≤ N ≤ 10 5 ), la tarea es encontrar el número de formas de seleccionar el triplete i, j y k tales que i < j < k y el producto arr[i] * arr[j] * arr[k] es positivo.
Nota: cada triplete puede consistir en un máximo de un elemento negativo.
Ejemplos:
Entrada: arr[] = {2, 5, -9, -3, 6}
Salida: 1
Explicación: El número total de formas de obtener un triplete i, j y k para satisfacer las condiciones dadas es 1 {0, 1, 4} .Entrada: arr[] = {2, 5, 6, -2, 5}
Salida: 4
Explicación: El número total de formas de obtener un triplete i, j y k para satisfacer las condiciones dadas es 4 {0, 1, 2}, {0, 1, 4}, {1, 2, 4} y {0, 2, 4}.
Enfoque: Todas las combinaciones posibles de un triplete son las siguientes:
- # elementos negativos o 2 elementos negativos y 1 elemento positivo. Ambas combinaciones no pueden considerarse como el máximo de elementos negativos permitidos en un triplete es 1.
- 2 elementos negativos ( -ve ) y 1 elemento positivo ( +ve) . Como el producto del triplete será negativo, no se puede considerar el triplete.
- 3 elementos positivos.
Siga los pasos a continuación para resolver el problema:
- Atraviese la array y cuente la frecuencia de los elementos positivos de la array, digamos freq .
- Recuento de formas de seleccionar un triplete válido del número de frecuencia de los elementos de la array mediante la fórmula PnC = N C 3 = (N * (N – 1) * (N – 2)) / 6 . Agregue el conteo obtenido a la respuesta.
- Imprime el conteo obtenido.
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 calculate // possible number of triplets long long int possibleTriplets(int arr[], int N) { int freq = 0; // counting frequency of positive numbers // in array for (int i = 0; i < N; i++) { // If current array // element is positive if (arr[i] > 0) { // Increment frequency freq++; } } // Select a triplet from freq // elements such that i < j < k. return (freq * 1LL * (freq - 1) * (freq - 2)) / 6; } // Driver Code int main() { int arr[] = { 2, 5, -9, -3, 6 }; int N = sizeof(arr) / sizeof(arr[0]); cout << possibleTriplets(arr, N); return 0; }
Java
// Java Program to implement // the above approach import java.util.*; class GFG { // Function to calculate // possible number of triplets static int possibleTriplets(int arr[], int N) { int freq = 0; // counting frequency of positive numbers // in array for (int i = 0; i < N; i++) { // If current array // element is positive if (arr[i] > 0) { // Increment frequency freq++; } } // Select a triplet from freq // elements such that i < j < k. return (int) ((freq * 1L * (freq - 1) * (freq - 2)) / 6); } // Driver Code public static void main(String[] args) { int arr[] = { 2, 5, -9, -3, 6 }; int N = arr.length; System.out.print(possibleTriplets(arr, N)); } } // This code is contributed by 29AjayKumar
Python3
# Python3 Program to implement # the above approach # Function to calculate # possible number of triplets def possibleTriplets(arr, N): freq = 0 # counting frequency of positive numbers # in array for i in range(N): # If current array # element is positive if (arr[i] > 0): # Increment frequency freq += 1 # Select a triplet from freq # elements such that i < j < k. return (freq * (freq - 1) * (freq - 2)) // 6 # Driver Code if __name__ == '__main__': arr = [2, 5, -9, -3, 6] N = len(arr) print(possibleTriplets(arr, N)) # This code is contributed by mohit kumar 29
C#
// C# Program to implement // the above approach using System; public class GFG { // Function to calculate // possible number of triplets static int possibleTriplets(int []arr, int N) { int freq = 0; // counting frequency of positive numbers // in array for (int i = 0; i < N; i++) { // If current array // element is positive if (arr[i] > 0) { // Increment frequency freq++; } } // Select a triplet from freq // elements such that i < j < k. return (int) ((freq * 1L * (freq - 1) * (freq - 2)) / 6); } // Driver Code public static void Main(String[] args) { int []arr = { 2, 5, -9, -3, 6 }; int N = arr.Length; Console.Write(possibleTriplets(arr, N)); } } // This code is contributed by 29AjayKumar
Javascript
<script> // Javascript Program to implement // the above approach // Function to calculate // possible number of triplets function possibleTriplets(arr, N) { var freq = 0; // counting frequency of positive numbers // in array for (var i = 0; i < N; i++) { // If current array // element is positive if (arr[i] > 0) { // Increment frequency freq++; } } // Select a triplet from freq // elements such that i < j < k. return (freq * 1 * (freq - 1) * (freq - 2)) / 6; } // Driver Code var arr = [ 2, 5, -9, -3, 6 ]; var N = arr.length; document.write( possibleTriplets(arr, N)); </script>
1
Complejidad de Tiempo : O(N)
Espacio Auxiliar : O(1)
Publicación traducida automáticamente
Artículo escrito por shubhampokhriyal2018 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA