Dado un arreglo A[ ] que consta de N enteros positivos, la tarea es encontrar el número de tripletes A[i], A[j] y A[k] en el arreglo tal que i < j < k y A[i] * A[j] = A[k] .
Ejemplos:
Entrada: N = 5, A[ ] = {2, 3, 4, 6, 12}
Salida: 3
Explicación:
Los tripletes válidos de la array dada son:
(A[0], A[1], A[3] ) = (2, 3, 6) donde (2*3 = 6)
(A[0], A[3], A[4]) = (2, 6, 12) donde (2*6 = 12)
( A[1], A[2], A[4]) = (3, 4, 12) donde (3*4 = 12)
Por lo tanto, existe un total de 3 tripletes que satisfacen la condición dada.
Entrada: N = 3, A[ ] = {1, 1, 1}
Salida: 1
Explicación:
El único triplete válido es (A[0], A[1], A[2]) = (1, 1, 1 )
Enfoque ingenuo:
el enfoque más simple para resolver el problema es generar todos los tripletes posibles y, para cada triplete, verificar si satisface la condición requerida. Si se determina que es cierto, aumente el conteo de trillizos. Después de completar el recorrido de la array y generar todos los tripletes posibles, imprima el recuento final .
Complejidad de tiempo: O(N 3 )
Espacio auxiliar: O(1)
Enfoque eficiente:
El enfoque anterior puede optimizarse utilizando Two Pointers y HashMap .
Siga los pasos a continuación para resolver el problema:
- Inicialice un mapa para almacenar frecuencias de elementos de array.
- Iterar sobre la array a la inversa, es decir, hacer un bucle con una variable j en el rango [N – 2, 1] .
- Por cada j , aumente la cuenta de A[j + 1] en el mapa. Itere sobre el rango [0, j – 1] usando la variable i y verifique si A[i] * A[j] está presente en el mapa o no.
- Si se encuentra A[i] * A[j] en el mapa, aumente el conteo de trillizos por la frecuencia de A[i] * A[j] almacenada en el mapa.
- Después de completar el recorrido de la array, imprima el conteo final .
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;
// Returns total number of
// valid triplets possible
int countTriplets(int A[], int N)
{
// Stores the count
int ans = 0;
// Map to store frequency
// of array elements
map<int, int> map;
for (int j = N - 2; j >= 1; j--) {
// Increment the frequency
// of A[j+1] as it can be
// a valid A[k]
map[A[j + 1]]++;
for (int i = 0; i < j; i++) {
int target = A[i] * A[j];
// If target exists in the map
if (map.find(target)
!= map.end())
ans += map[target];
}
}
// Return the final count
return ans;
}
// Driver Code
int main()
{
int N = 5;
int A[] = { 2, 3, 4, 6, 12 };
cout << countTriplets(A, N);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Returns total number of
// valid triplets possible
static int countTriplets(int A[], int N)
{
// Stores the count
int ans = 0;
// Map to store frequency
// of array elements
HashMap<Integer,
Integer> map = new HashMap<Integer,
Integer>();
for(int j = N - 2; j >= 1; j--)
{
// Increment the frequency
// of A[j+1] as it can be
// a valid A[k]
if(map.containsKey(A[j + 1]))
map.put(A[j + 1], map.get(A[j + 1]) + 1);
else
map.put(A[j + 1], 1);
for(int i = 0; i < j; i++)
{
int target = A[i] * A[j];
// If target exists in the map
if (map.containsKey(target))
ans += map.get(target);
}
}
// Return the final count
return ans;
}
// Driver Code
public static void main(String[] args)
{
int N = 5;
int A[] = { 2, 3, 4, 6, 12 };
System.out.print(countTriplets(A, N));
}
}
// This code is contributed by sapnasingh4991
Python3
# Python3 program for the above approach from collections import defaultdict # Returns total number of # valid triplets possible def countTriplets(A, N): # Stores the count ans = 0 # Map to store frequency # of array elements map = defaultdict(lambda: 0) for j in range(N - 2, 0, -1): # Increment the frequency # of A[j+1] as it can be # a valid A[k] map[A[j + 1]] += 1 for i in range(j): target = A[i] * A[j] # If target exists in the map if(target in map.keys()): ans += map[target] # Return the final count return ans # Driver code if __name__ == '__main__': N = 5 A = [ 2, 3, 4, 6, 12 ] print(countTriplets(A, N)) # This code is contributed by Shivam Singh
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Returns total number of
// valid triplets possible
static int countTriplets(int []A, int N)
{
// Stores the count
int ans = 0;
// Map to store frequency
// of array elements
Dictionary<int,
int> map = new Dictionary<int,
int>();
for(int j = N - 2; j >= 1; j--)
{
// Increment the frequency
// of A[j+1] as it can be
// a valid A[k]
if(map.ContainsKey(A[j + 1]))
map[A[j + 1]] = map[A[j + 1]] + 1;
else
map.Add(A[j + 1], 1);
for(int i = 0; i < j; i++)
{
int target = A[i] * A[j];
// If target exists in the map
if (map.ContainsKey(target))
ans += map[target];
}
}
// Return the readonly count
return ans;
}
// Driver Code
public static void Main(String[] args)
{
int N = 5;
int []A = { 2, 3, 4, 6, 12 };
Console.Write(countTriplets(A, N));
}
}
// This code is contributed by sapnasingh4991
Javascript
<script>
// Javascript program to implement
// the above approach
// Returns total number of
// valid triplets possible
function countTriplets(A, N)
{
// Stores the count
let ans = 0;
// Map to store frequency
// of array elements
let map = new Map();
for(let j = N - 2; j >= 1; j--)
{
// Increment the frequency
// of A[j+1] as it can be
// a valid A[k]
if(map.has(A[j + 1]))
map.set(A[j + 1], map.get(A[j + 1]) + 1);
else
map.set(A[j + 1], 1);
for(let i = 0; i < j; i++)
{
let target = A[i] * A[j];
// If target exists in the map
if (map.has(target))
ans += map.get(target);
}
}
// Return the final count
return ans;
}
// Driver code
let N = 5;
let A = [ 2, 3, 4, 6, 12 ];
document.write(countTriplets(A, N));
// This code is contributed by souravghosh0416.
</script>
3
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(N)