Dada una array de enteros con elementos duplicados . La tarea es encontrar el producto de todos los elementos distintos en la array dada.
Ejemplos :
Entrada : arr[] = {12, 10, 9, 45, 2, 10, 10, 45, 10};
Salida : 97200
Aquí tomamos 12, 10, 9, 45, 2 para el producto
porque estos son los únicos elementos distintosEntrada : arr[] = {1, 10, 9, 4, 2, 10, 10, 45, 4};
Salida : 32400
Una solución simple es usar dos bucles anidados. El bucle exterior elige un elemento uno por uno comenzando desde el elemento más a la izquierda. El bucle interno verifica si el elemento está presente en el lado izquierdo. Si está presente, ignora el elemento.
Complejidad de Tiempo : O(N 2 )
Espacio Auxiliar : O(1)
Una mejor solución a este problema es ordenar primero todos los elementos de la array en orden ascendente y encontrar uno por uno los elementos distintos en la array. Finalmente, encuentre el producto de todos los elementos distintos.
A continuación se muestra la implementación de este enfoque:
C++
// C++ program to find the product of all
// non-repeated elements in an array
#include <bits/stdc++.h>
using namespace std;
// Function to find the product of all
// non-repeated elements in an array
int findProduct(int arr[], int n)
{
// sort all elements of array
sort(arr, arr + n);
int prod = 1;
for (int i = 0; i < n; i++) {
if (arr[i] != arr[i + 1])
prod = prod * arr[i];
}
return prod;
}
// Driver code
int main()
{
int arr[] = { 1, 2, 3, 1, 1, 4, 5, 6 };
int n = sizeof(arr) / sizeof(int);
cout << findProduct(arr, n);
return 0;
}
Java
// Java program to find the product of all
// non-repeated elements in an array
import java.util.Arrays;
class GFG {
// Function to find the product of all
// non-repeated elements in an array
static int findProduct(int arr[], int n)
{
// sort all elements of array
Arrays.sort(arr);
int prod = 1 * arr[0];
for (int i = 0; i < n - 1; i++)
{
if (arr[i] != arr[i + 1])
{
prod = prod * arr[i + 1];
}
}
return prod;
}
// Driver code
public static void main(String[] args) {
int arr[] = {1, 2, 3, 1, 1, 4, 5, 6};
int n = arr.length;
System.out.println(findProduct(arr, n));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python 3 program to find the product # of all non-repeated elements in an array # Function to find the product of all # non-repeated elements in an array def findProduct(arr, n): # sort all elements of array sorted(arr) prod = 1 for i in range(0, n, 1): if (arr[i - 1] != arr[i]): prod = prod * arr[i] return prod; # Driver code if __name__ == '__main__': arr = [1, 2, 3, 1, 1, 4, 5, 6] n = len(arr) print(findProduct(arr, n)) # This code is contributed by # Surendra_Gangwar
C#
// C# program to find the product of all
// non-repeated elements in an array
using System;
class GFG
{
// Function to find the product of all
// non-repeated elements in an array
static int findProduct(int []arr, int n)
{
// sort all elements of array
Array.Sort(arr);
int prod = 1 * arr[0];
for (int i = 0; i < n - 1; i++)
{
if (arr[i] != arr[i + 1])
{
prod = prod * arr[i + 1];
}
}
return prod;
}
// Driver code
public static void Main()
{
int []arr = {1, 2, 3, 1, 1, 4, 5, 6};
int n = arr.Length;
Console.WriteLine(findProduct(arr, n));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// javascript program to find the product of all
// non-repeated elements in an array
// Function to find the product of all
// non-repeated elements in an array
function findProduct(arr , n) {
// sort all elements of array
arr.sort();
var prod = 1 * arr[0];
for (i = 0; i < n - 1; i++) {
if (arr[i] != arr[i + 1]) {
prod = prod * arr[i + 1];
}
}
return prod;
}
// Driver code
var arr = [ 1, 2, 3, 1, 1, 4, 5, 6 ];
var n = arr.length;
document.write(findProduct(arr, n));
// This code contributed by gauravrajput1
</script>
720
Complejidad de tiempo : O(N * logN)
Espacio auxiliar : O(1)
Una solución eficiente es atravesar la array y mantener un mapa hash para verificar si el elemento se repite o no. Al atravesar si el elemento actual ya está presente en el hash o no, si es así, significa que se repite y no debe multiplicarse con el producto, si no está presente en el hash, multiplíquelo con el producto e insértelo en picadillo.
A continuación se muestra la implementación de este enfoque:
CPP
// C++ program to find the product of all
// non- repeated elements in an array
#include <bits/stdc++.h>
using namespace std;
// Function to find the product of all
// non-repeated elements in an array
int findProduct(int arr[], int n)
{
int prod = 1;
// Hash to store all element of array
unordered_set<int> s;
for (int i = 0; i < n; i++) {
if (s.find(arr[i]) == s.end()) {
prod *= arr[i];
s.insert(arr[i]);
}
}
return prod;
}
// Driver code
int main()
{
int arr[] = { 1, 2, 3, 1, 1, 4, 5, 6 };
int n = sizeof(arr) / sizeof(int);
cout << findProduct(arr, n);
return 0;
}
Java
// Java program to find the product of all
// non- repeated elements in an array
import java.util.HashSet;
class GFG
{
// Function to find the product of all
// non-repeated elements in an array
static int findProduct(int arr[], int n)
{
int prod = 1;
// Hash to store all element of array
HashSet<Integer> s = new HashSet<>();
for (int i = 0; i < n; i++)
{
if (!s.contains(arr[i]))
{
prod *= arr[i];
s.add(arr[i]);
}
}
return prod;
}
// Driver code
public static void main(String[] args)
{
int arr[] = {1, 2, 3, 1, 1, 4, 5, 6};
int n = arr.length;
System.out.println(findProduct(arr, n));
}
}
/* This code contributed by PrinciRaj1992 */
Python
# Python3 program to find the product of all # non- repeated elements in an array # Function to find the product of all # non-repeated elements in an array def findProduct( arr, n): prod = 1 # Hash to store all element of array s = dict() for i in range(n): if (arr[i] not in s.keys()): prod *= arr[i] s[arr[i]] = 1 return prod # Driver code arr= [1, 2, 3, 1, 1, 4, 5, 6] n = len(arr) print(findProduct(arr, n)) # This code is contributed by mohit kumar
C#
// C# program to find the product of all
// non- repeated elements in an array
using System;
using System.Collections.Generic;
class GFG
{
// Function to find the product of all
// non-repeated elements in an array
static int findProduct(int []arr, int n)
{
int prod = 1;
// Hash to store all element of array
HashSet<int> s = new HashSet<int>();
for (int i = 0; i < n; i++)
{
if (!s.Contains(arr[i]))
{
prod *= arr[i];
s.Add(arr[i]);
}
}
return prod;
}
// Driver code
public static void Main(String[] args)
{
int []arr = {1, 2, 3, 1, 1, 4, 5, 6};
int n = arr.Length;
Console.WriteLine(findProduct(arr, n));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// JavaScript program to find the product of all
// non- repeated elements in an array
// Function to find the product of all
// non-repeated elements in an array
function findProduct(arr,n)
{
let prod = 1;
// Hash to store all element of array
let s = new Set();
for (let i = 0; i < n; i++)
{
if (!s.has(arr[i]))
{
prod *= arr[i];
s.add(arr[i]);
}
}
return prod;
}
// Driver code
let arr=[1, 2, 3, 1, 1, 4, 5, 6];
let n = arr.length;
document.write(findProduct(arr, n));
// This code is contributed by patel2127
</script>
720
Tiempo Complejidad : O(N)
Espacio Auxiliar : O(N)
Otro enfoque (usando las funciones integradas de Python): pasos para encontrar el producto de elementos únicos:
- Calcule las frecuencias usando la función Counter()
- Convierte las claves de frecuencia a la lista.
- Calcular el producto de la lista.
A continuación se muestra la implementación de este enfoque:
Python3
# Python program for the above approach from collections import Counter # Function to return the product of distinct elements def sumOfElements(arr, n): # Counter function is used to # calculate frequency of elements of array freq = Counter(arr) # Converting keys of freq dictionary to list lis = list(freq.keys()) # Return product of list product=1 for i in lis: product*=i return product # Driver code if __name__ == "__main__": arr = [1, 2, 3, 1, 1, 4, 5, 6] n = len(arr) print(sumOfElements(arr, n)) # This code is contributed by Pushpesh Raj
720
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por VishalBachchas y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA