Dada una array arr[] que consta de N enteros positivos, la tarea es encontrar el número de subsecuencias de longitud 4 que tengan el producto de los tres primeros elementos igual al cuarto elemento.
Ejemplos:
Entrada: arr[] = {10, 2, 2, 7, 40, 160}
Salida: 2
Explicación: Las
siguientes son las subsecuencias de longitud 4 que satisfacen los criterios dados:
- {10, 2, 2, 40}, el producto de los tres primeros elementos es 10*2*2 = 40(= cuarto elemento).
- {2, 2, 40, 160}, el producto de los tres primeros elementos es 2*2*40 = 160(= cuarto elemento).
Por lo tanto, el recuento total de subsecuencias es 2.
Entrada: arr[] = {1, 1, 1, 1}
Salida: 1
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todas las subsecuencias posibles y contar aquellas subsecuencias que satisfacen los criterios dados. Después de verificar todas las subsecuencias, imprima el recuento total obtenido.
Complejidad temporal: O(2 N )
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar encontrando todas las subsecuencias de longitud 3 y almacenando el producto de los tres en HashMap y luego contando la subsecuencia fijando cada elemento como el cuarto elemento e incrementando la frecuencia del producto de tripletes. Siga los pasos a continuación para resolver el problema dado:
- Inicialice una variable, digamos ans como 0 , que almacene el recuento de las subsecuencias resultantes.
- Inicialice un mapa desordenado, digamos M , que almacene las frecuencias del producto de tripletes .
- Recorra la array dada usando la variable i y realice los siguientes pasos:
- Incremente el valor de ans por arr[i] considerándolo como el cuarto elemento de la subsecuencia.
- Genere todos los pares posibles de la array en el rango [0, i – 1] y almacene la frecuencia del producto de los dos con arr[i] en el mapa M .
- Después de completar los pasos anteriores, imprima el valor de ans como el recuento resultante de subsecuencias.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the total number of
// subsequences satisfying the given
// criteria
int countQuadruples(int A[], int N)
{
// Stores the count of quadruplets
int ans = 0;
// Stores the frequency of product
// of the triplet
unordered_map<int, int> freq;
// Traverse the given array arr[]
for (int i = 0; i < N; i++) {
// Consider arr[i] as fourth
// element of subsequences
ans += freq[A[i]];
// Generate all possible pairs
// of the array [0, i - 1]
for (int j = 0; j < i; j++) {
for (int k = 0; k < j; k++) {
// Increment the frequency
// of the triplet
freq[A[i] * A[j] * A[k]]++;
}
}
}
// Return the total count obtained
return ans;
}
// Driver Code
int main()
{
int arr[] = { 10, 2, 2, 7, 40, 160 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << countQuadruples(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to find the total number of
// subsequences satisfying the given
// criteria
static int countQuadruples(int A[], int N)
{
// Stores the count of quadruplets
int ans = 0;
// Stores the frequency of product
// of the triplet
HashMap<Integer, Integer> freq = new HashMap<Integer, Integer>();
// Traverse the given array arr[]
for (int i = 0; i < N; i++) {
// Consider arr[i] as fourth
// element of subsequences
if (freq.containsKey(A[i]))
ans += freq.get(A[i]);
// Generate all possible pairs
// of the array [0, i - 1]
for (int j = 0; j < i; j++) {
for (int k = 0; k < j; k++) {
// Increment the frequency
// of the triplet
if (freq.containsKey(A[i] * A[j] * A[k]))
{
freq.put(A[i] * A[j] * A[k], freq.get(A[i] * A[j] * A[k]) + 1);
}
else
{
freq.put(A[i] * A[j] * A[k], 1);
}
}
}
}
// Return the total count obtained
return ans;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 10, 2, 2, 7, 40, 160 };
int N = arr.length;
System.out.print(countQuadruples(arr, N));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python 3 program for the above approach
# Function to find the total number of
# subsequences satisfying the given
# criteria
def countQuadruples(A, N):
# Stores the count of quadruplets
ans = 0
# Stores the frequency of product
# of the triplet
freq = {}
# Traverse the given array arr[]
for i in range(N):
# Consider arr[i] as fourth
# element of subsequences
if A[i] in freq:
ans += freq[A[i]]
else:
freq[A[i]] = 0
# Generate all possible pairs
# of the array [0, i - 1]
for j in range(i):
for k in range(j):
# Increment the frequency
# of the triplet
if A[i] * A[j] * A[k] in freq:
freq[A[i] * A[j] * A[k]] += 1
else:
freq[A[i] * A[j] * A[k]] = 1
# Return the total count obtained
return ans
# Driver Code
if __name__ == '__main__':
arr = [10, 2, 2, 7, 40, 160]
N = len(arr)
print(countQuadruples(arr, N))
# This code is contributed by SURENDRA_GANGWAR.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the total number of
// subsequences satisfying the given
// criteria
static int countQuadruples(int []A, int N)
{
// Stores the count of quadruplets
int ans = 0;
// Stores the frequency of product
// of the triplet
Dictionary<int,int> freq = new Dictionary<int,int>();
// Traverse the given array arr[]
for (int i = 0; i < N; i++) {
// Consider arr[i] as fourth
// element of subsequences
if(freq.ContainsKey(A[i]))
ans += freq[A[i]];
else
freq.Add(A[i],0);
// Generate all possible pairs
// of the array [0, i - 1]
for (int j = 0; j < i; j++) {
for (int k = 0; k < j; k++) {
// Increment the frequency
// of the triplet
if(freq.ContainsKey(A[i] * A[j] * A[k]))
freq[A[i] * A[j] * A[k]]++;
else
freq.Add(A[i] * A[j] * A[k],1);
}
}
}
// Return the total count obtained
return ans;
}
// Driver Code
public static void Main()
{
int []arr = { 10, 2, 2, 7, 40, 160 };
int N = arr.Length;
Console.Write(countQuadruples(arr, N));
}
}
// This code is contributed by ipg2016107.
Javascript
<script>
// JavaScript program for the above approach;
// Function to find the total number of
// subsequences satisfying the given
// criteria
function countQuadruples(A, N)
{
// Stores the count of quadruplets
let ans = 0;
// Stores the frequency of product
// of the triplet
let freq = new Map();
// Traverse the given array arr[]
for (let i = 0; i < N; i++) {
// Consider arr[i] as fourth
// element of subsequences
if (freq.has(arr[i])) {
ans += freq.get(A[i]);
}
// Generate all possible pairs
// of the array [0, i - 1]
for (let j = 0; j < i; j++) {
for (let k = 0; k < j; k++) {
// Increment the frequency
// of the triplet
if (freq.has(A[i] * A[j] * A[k])) {
freq.set(freq.get(A[i] * A[j] * A[k]), freq.get([A[i] * A[j] * A[k]]) + 1);
}
else {
freq.set(A[i] * A[j] * A[k], 1);
}
}
}
}
// Return the total count obtained
return ans;
}
// Driver Code
let arr = [10, 2, 2, 7, 40, 160];
let N = arr.length;
document.write(countQuadruples(arr, N));
// This code is contributed by Potta Lokesh
</script>
Producción:
2
Complejidad temporal: O(N 3 )
Espacio auxiliar: O(N 3 )
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA