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>
4
Complejidad de tiempo: O(N * log(M)), donde M es el elemento más grande de la array arr[] Espacio auxiliar: O(N)