Dada una array arr[] que consta de N enteros positivos, la tarea es encontrar el MCM de todos los elementos únicos de la array dada . Si la array no contiene ningún elemento único, imprima «-1 «.
Ejemplos:
Entrada: arr[] = {1, 2, 1, 3, 3, 4}
Salida: 4
Explicación:
Los elementos únicos de la array dada son: 2 y 4. Por lo tanto, el MCM de (2, 4) es 4.Entrada: arr[] = {1, 1, 2, 2, 3, 3}
Salida: -1
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es recorrer la array dada arr[] para cada elemento de la array arr[i] y verificar si arr[i] es único o no. Si se encuentra que es cierto, guárdelo en otra array. Después de recorrer todos los elementos, imprima el LCM de los elementos presentes en la array recién creada .
Complejidad de tiempo: O(N 2 + N * log(M)), donde M es el elemento más grande de la array arr[] . Espacio Auxiliar: O(N)
Enfoque eficiente: el enfoque anterior también se puede optimizar utilizando Hashing para encontrar los elementos únicos en la array. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos ans como 1 para almacenar el LCM de los elementos únicos de la array.
- Recorra la array arr[] y almacene la frecuencia de cada elemento en el Mapa .
- Ahora, recorra el mapa y si el recuento de cualquier elemento es igual a 1 , actualice el valor de ans a LCM de ans y el elemento actual .
- Después de completar los pasos anteriores, si el valor de ans es 1 , imprima «-1» . De lo contrario, imprime el valor de ans como resultado.
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 GCD of two numbers
int findGCD(int a, int b)
{
// Base Case
if (b == 0)
return a;
// Recursively find the GCD
return findGCD(b, a % b);
}
// Function to find LCM of two numbers
int findLCM(int a, int b)
{
return (a * b) / findGCD(a, b);
}
// Function to find LCM of unique elements
// present in the array
int uniqueElementsLCM(int arr[], int N)
{
// Stores the frequency of each
// number of the array
unordered_map<int, int> freq;
// Store the frequency of each
// element of the array
for (int i = 0; i < N; i++) {
freq[arr[i]]++;
}
// Store the required result
int lcm = 1;
// Traverse the map freq
for (auto i : freq) {
// If the frequency of the
// current element is 1, then
// update ans
if (i.second == 1) {
lcm = findLCM(lcm, i.first);
}
}
// If there is no unique element,
// set lcm to -1
if (lcm == 1)
lcm = -1;
// Print the result
cout << lcm;
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 1, 3, 3, 4 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
uniqueElementsLCM(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.HashMap;
import java.util.Map.Entry;
class GFG{
// Function to find GCD of two numbers
static int findGCD(int a, int b)
{
// Base Case
if (b == 0)
return a;
// Recursively find the GCD
return findGCD(b, a % b);
}
// Function to find LCM of two numbers
static int findLCM(int a, int b)
{
return (a * b) / findGCD(a, b);
}
// Function to find LCM of unique elements
// present in the array
static void uniqueElementsLCM(int arr[], int N)
{
// Stores the frequency of each
// number of the array
HashMap<Integer,
Integer> freq = new HashMap<Integer,
Integer>();
// Store the frequency of each
// element of the array
for(int i = 0; i < N; i++)
{
freq.put(arr[i],
freq.getOrDefault(arr[i], 0) + 1);
}
// Store the required result
int lcm = 1;
// Traverse the map freq
for(Entry<Integer, Integer> i : freq.entrySet())
{
// If the frequency of the
// current element is 1, then
// update ans
if (i.getValue() == 1)
{
lcm = findLCM(lcm, i.getKey());
}
}
// If there is no unique element,
// set lcm to -1
if (lcm == 1)
lcm = -1;
// Print the result
System.out.print(lcm);
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 2, 1, 3, 3, 4 };
int N = arr.length;
// Function Call
uniqueElementsLCM(arr, N);
}
}
// This code is contributed by abhinavjain194
Python3
# Python3 program for the above approach from collections import defaultdict # Function to find GCD of two numbers def findGCD(a, b): # Base Case if (b == 0): return a # Recursively find the GCD return findGCD(b, a % b) # Function to find LCM of two numbers def findLCM(a, b): return (a * b) // findGCD(a, b) # Function to find LCM of unique elements # present in the array def uniqueElementsLCM(arr, N): # Stores the frequency of each # number of the array freq = defaultdict(int) # Store the frequency of each # element of the array for i in range(N): freq[arr[i]] += 1 # Store the required result lcm = 1 # Traverse the map freq for i in freq: # If the frequency of the # current element is 1, then # update ans if (freq[i] == 1): lcm = findLCM(lcm, i) # If there is no unique element, # set lcm to -1 if (lcm == 1): lcm = -1 # Print the result print(lcm) # Driver Code if __name__ == "__main__": arr = [ 1, 2, 1, 3, 3, 4 ] N = len(arr) # Function Call uniqueElementsLCM(arr, N) # This code is contributed by ukasp
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find GCD of two numbers
static int findGCD(int a, int b)
{
// Base Case
if (b == 0)
return a;
// Recursively find the GCD
return findGCD(b, a % b);
}
// Function to find LCM of two numbers
static int findLCM(int a, int b)
{
return (a * b) / findGCD(a, b);
}
// Function to find LCM of unique elements
// present in the array
static void uniqueElementsLCM(int []arr, int N)
{
// Stores the frequency of each
// number of the array
Dictionary<int,int> freq = new Dictionary<int,int>();
// Store the frequency of each
// element of the array
for (int i = 0; i < N; i++) {
if(freq.ContainsKey(arr[i]))
freq[arr[i]]++;
else
freq.Add(arr[i],1);
}
// Store the required result
int lcm = 1;
// Traverse the map freq
foreach(KeyValuePair<int, int> kvp in freq) {
// If the frequency of the
// current element is 1, then
// update ans
if (kvp.Value == 1) {
lcm = findLCM(lcm, kvp.Key);
}
}
// If there is no unique element,
// set lcm to -1
if (lcm == 1)
lcm = -1;
// Print the result
Console.Write(lcm);
}
// Driver Code
public static void Main()
{
int []arr = {1, 2, 1, 3, 3, 4 };
int N = arr.Length;
// Function Call
uniqueElementsLCM(arr, N);
}
}
// This code is contributed by ipg2016107.
Javascript
<script>
// Javascript program for the above approach
// Function to find GCD of two numbers
function findGCD(a, b)
{
// Base Case
if (b == 0)
return a;
// Recursively find the GCD
return findGCD(b, a % b);
}
// Function to find LCM of two numbers
function findLCM(a, b)
{
return (a * b) / findGCD(a, b);
}
// Function to find LCM of unique elements
// present in the array
function uniqueElementsLCM(arr, N)
{
// Stores the frequency of each
// number of the array
var freq = new Map();
// Store the frequency of each
// element of the array
for (var i = 0; i < N; i++) {
if(freq.has(arr[i]))
{
freq.set(arr[i], freq.get(arr[i])+1);
}
else
{
freq.set(arr[i], 1);
}
}
// Store the required result
var lcm = 1;
// Traverse the map freq
freq.forEach((value, key) => {
// If the frequency of the
// current element is 1, then
// update ans
if (value == 1) {
lcm = findLCM(lcm, key);
}
});
// If there is no unique element,
// set lcm to -1
if (lcm == 1)
lcm = -1;
// Print the result
document.write( lcm);
}
// Driver Code
var arr = [1, 2, 1, 3, 3, 4];
var N = arr.length;
// Function Call
uniqueElementsLCM(arr, N);
</script>
Producción:
4
Complejidad de tiempo: O(N * log(M)), donde M es el elemento más grande de la array arr[] Espacio auxiliar: O(N)