Dada una array arr de tamaño N que contiene números en el rango [1, M] , la tarea es encontrar un elemento, en el rango [1, M] , que maximice el MCM.
Ejemplos:
Entrada: arr[]={3, 4, 2, 7}, M = 8
Salida: 5
Explicación:
El MCM de la array existente (3, 4, 2, 7) = 84
Sumar los números restantes del 1 al 8 y verificar el LCM correspondiente de la array resultante.
1: MCM de (1, 3, 4, 2, 7) es 84
5: MCM de (5, 3, 4, 2, 7) es 420
6: MCM de (6, 3, 4, 2, 7) es 84
8: MCM de (5, 3, 4, 2, 7) es 168
Claramente, sumar 5 maximiza el MCM.
Entrada: arr[]={2, 5, 3, 8, 1}, M = 9
Salida: 7
Enfoque ingenuo:
- Calcule el LCM de la array dada.
- Calcule el LCM después de agregar cada elemento en el rango [1, M] que no está presente en la array y devuelva el elemento para el cual es máximo.
Enfoque eficiente:
- Precalcular los factores primos , de números hasta 1000, usando Sieve .
- Almacene la frecuencia de cada factor primo del MCM de la array dada.
- Iterar a partir de los valores [1, M] y, para cada valor que no esté presente en la array, calcular el producto de las diferencias en las frecuencias de los factores primos de ese número y el MCM de la array dada.
- Devuelve el elemento que proporciona el máximo producto.
El siguiente código es la implementación del enfoque anterior:
C++
// C++ program to find the element // to be added to maximize the LCM #include <bits/stdc++.h> using namespace std; // Vector which stores the prime factors // of all the numbers upto 10000 vector<int> primeFactors[10001]; set<int> s; // Function which finds prime // factors using sieve method void findPrimeFactors() { // Boolean array which stores // true if the index is prime bool primes[10001]; memset(primes, true, sizeof(primes)); // Sieve of Eratosthenes for (int i = 2; i < 10001; i++) { if (primes[i]) { for (int j = i; j < 10001; j += i) { if (j != i) { primes[j] = false; } primeFactors[j].push_back(i); } } } } // Function which stores frequency of every // prime factor of LCM of the initial array void primeFactorsofLCM(int* frequecyOfPrimes, int* arr, int n) { for (int i = 0; i < n; i++) { for (auto a : primeFactors[arr[i]]) { int k = 0; // While the prime factor // divides the number while ((arr[i] % a) == 0) { arr[i] /= a; k++; } frequecyOfPrimes[a] = max(frequecyOfPrimes[a], k); } } } // Function which returns the element // which should be added to array int elementToBeAdded(int* frequecyOfPrimes, int m) { int product = 1; // To store the final answer int ans = 1; for (int i = 2; i <= m; i++) { if (s.find(i) != s.end()) continue; int j = i; int current = 1; for (auto a : primeFactors[j]) { int k = 0; // While the prime factor // divides the number while ((j % a) == 0) { j /= a; k++; if (k > frequecyOfPrimes[a]) { current *= a; } } } // Check element which provides // the maximum product if (current > product) { product = current; ans = i; } } return ans; } void findElement(int* arr, int n, int m) { for (int i = 0; i < n; i++) s.insert(arr[i]); int frequencyOfPrimes[10001] = { 0 }; primeFactorsofLCM(frequencyOfPrimes, arr, n); cout << elementToBeAdded(frequencyOfPrimes, m) << endl; } // Driver code int main() { // Precomputing the prime factors // of all numbers upto 10000 findPrimeFactors(); int N = 5; int M = 9; int arr[] = { 2, 5, 3, 8, 1 }; findElement(arr, N, M); return 0; }
Java
// Java program to find the element // to be added to maximize the LCM import java.util.*; class GFG{ // Vector which stores the prime factors // of all the numbers upto 10000 static Vector<Integer> []primeFactors = new Vector[10001]; static HashSet<Integer> s = new HashSet<Integer>(); // Function which finds prime // factors using sieve method static void findPrimeFactors() { // Boolean array which stores // true if the index is prime boolean []primes = new boolean[10001]; Arrays.fill(primes, true); // Sieve of Eratosthenes for (int i = 2; i < 10001; i++) { if (primes[i]) { for (int j = i; j < 10001; j += i) { if (j != i) { primes[j] = false; } primeFactors[j].add(i); } } } } // Function which stores frequency of every // prime factor of LCM of the initial array static void primeFactorsofLCM(int []frequecyOfPrimes, int[] arr, int n) { for (int i = 0; i < n; i++) { for (int a : primeFactors[arr[i]]) { int k = 0; // While the prime factor // divides the number while ((arr[i] % a) == 0) { arr[i] /= a; k++; } frequecyOfPrimes[a] = Math.max(frequecyOfPrimes[a], k); } } } // Function which returns the element // which should be added to array static int elementToBeAdded(int []frequecyOfPrimes, int m) { int product = 1; // To store the final answer int ans = 1; for (int i = 2; i <= m; i++) { if (s.contains(i)) continue; int j = i; int current = 1; for (int a : primeFactors[j]) { int k = 0; // While the prime factor // divides the number while ((j % a) == 0) { j /= a; k++; if (k > frequecyOfPrimes[a]) { current *= a; } } } // Check element which provides // the maximum product if (current > product) { product = current; ans = i; } } return ans; } static void findElement(int[] arr, int n, int m) { for (int i = 0; i < n; i++) s.add(arr[i]); int frequencyOfPrimes[] = new int[10001]; primeFactorsofLCM(frequencyOfPrimes, arr, n); System.out.print(elementToBeAdded(frequencyOfPrimes, m) +"\n"); } // Driver code public static void main(String[] args) { for (int i = 0; i < 10001; i++) primeFactors[i] = new Vector<Integer>(); // Precomputing the prime factors // of all numbers upto 10000 findPrimeFactors(); int N = 5; int M = 9; int arr[] = { 2, 5, 3, 8, 1 }; findElement(arr, N, M); } } // This code is contributed by Rajput-Ji
Python3
# Python3 program to find the element # to be added to maximize the LCM # Vector which stores the prime factors # of all the numbers upto 10000 primeFactors = [[] for i in range(10001)] s = set() # Function which finds prime # factors using sieve method def findPrimeFactors(): # Boolean array which stores # true if the index is prime primes = [True for i in range(10001)] # Sieve of Eratosthenes for i in range(2,10001): if (primes[i]): for j in range(i,10001,i): if (j != i): primes[j] = False primeFactors[j].append(i) # Function which stores frequency of every # prime factor of LCM of the initial array def primeFactorsofLCM(frequecyOfPrimes, arr, n): for i in range(n): for a in primeFactors[arr[i]]: k = 0 # While the prime factor # divides the number while ((arr[i] % a) == 0): arr[i] = arr[i] // a k += 1 frequecyOfPrimes[a] = max(frequecyOfPrimes[a], k) # Function which returns the element # which should be added to array def elementToBeAdded(frequecyOfPrimes, m): product = 1 # To store the final answer ans = 1 for i in range(2,m+1): if (i in s): continue j = i current = 1 for a in primeFactors[j]: k = 0 # While the prime factor # divides the number while ((j % a) == 0): j = j // a k += 1 if (k > frequecyOfPrimes[a]): current *= a # Check element which provides # the maximum product if (current > product): product = current ans = i return ans def findElement(arr, n, m): for i in range(n): s.add(arr[i]) frequencyOfPrimes = [0 for i in range(10001)] primeFactorsofLCM(frequencyOfPrimes, arr, n) print(elementToBeAdded(frequencyOfPrimes, m)) # Driver code # Precomputing the prime factors # of all numbers upto 10000 findPrimeFactors() N = 5 M = 9 arr = [ 2, 5, 3, 8, 1 ] findElement(arr, N, M) # This code is contributed by shinjanpatra
C#
// C# program to find the element // to be added to maximize the LCM using System; using System.Collections.Generic; class GFG{ // List which stores the prime factors // of all the numbers upto 10000 static List<int> []primeFactors = new List<int>[10001]; static HashSet<int> s = new HashSet<int>(); // Function which finds prime // factors using sieve method static void findPrimeFactors() { // Boolean array which stores // true if the index is prime bool []primes = new bool[10001]; for (int i = 0; i < 10001; i++) primes[i] = true; // Sieve of Eratosthenes for (int i = 2; i < 10001; i++) { if (primes[i]) { for (int j = i; j < 10001; j += i) { if (j != i) { primes[j] = false; } primeFactors[j].Add(i); } } } } // Function which stores frequency of every // prime factor of LCM of the initial array static void primeFactorsofLCM(int []frequecyOfPrimes, int[] arr, int n) { for (int i = 0; i < n; i++) { foreach (int a in primeFactors[arr[i]]) { int k = 0; // While the prime factor // divides the number while ((arr[i] % a) == 0) { arr[i] /= a; k++; } frequecyOfPrimes[a] = Math.Max(frequecyOfPrimes[a], k); } } } // Function which returns the element // which should be added to array static int elementToBeAdded(int []frequecyOfPrimes, int m) { int product = 1; // To store the readonly answer int ans = 1; for (int i = 2; i <= m; i++) { if (s.Contains(i)) continue; int j = i; int current = 1; foreach (int a in primeFactors[j]) { int k = 0; // While the prime factor // divides the number while ((j % a) == 0) { j /= a; k++; if (k > frequecyOfPrimes[a]) { current *= a; } } } // Check element which provides // the maximum product if (current > product) { product = current; ans = i; } } return ans; } static void findElement(int[] arr, int n, int m) { for (int i = 0; i < n; i++) s.Add(arr[i]); int []frequencyOfPrimes = new int[10001]; primeFactorsofLCM(frequencyOfPrimes, arr, n); Console.Write(elementToBeAdded(frequencyOfPrimes, m) +"\n"); } // Driver code public static void Main(String[] args) { for (int i = 0; i < 10001; i++) primeFactors[i] = new List<int>(); // Precomputing the prime factors // of all numbers upto 10000 findPrimeFactors(); int N = 5; int M = 9; int []arr = { 2, 5, 3, 8, 1 }; findElement(arr, N, M); } } // This code is contributed by PrinciRaj1992
Javascript
<script> // Javascript program to find the element // to be added to maximize the LCM // Vector which stores the prime factors // of all the numbers upto 10000 let primeFactors = new Array(); for(let i = 0; i < 10001; i++){ primeFactors.push([]) } let s = new Set(); // Function which finds prime // factors using sieve method function findPrimeFactors() { // Boolean array which stores // true if the index is prime let primes = new Array(10001); primes.fill(true) // Sieve of Eratosthenes for (let i = 2; i < 10001; i++) { if (primes[i]) { for (let j = i; j < 10001; j += i) { if (j != i) { primes[j] = false; } primeFactors[j].push(i); } } } } // Function which stores frequency of every // prime factor of LCM of the initial array function primeFactorsofLCM(frequecyOfPrimes, arr, n) { for (let i = 0; i < n; i++) { for (let a of primeFactors[arr[i]]) { let k = 0; // While the prime factor // divides the number while ((arr[i] % a) == 0) { arr[i] /= a; k++; } frequecyOfPrimes[a] = Math.max(frequecyOfPrimes[a], k); } } } // Function which returns the element // which should be added to array function elementToBeAdded(frequecyOfPrimes, m) { let product = 1; // To store the final answer let ans = 1; for (let i = 2; i <= m; i++) { if (s.has(i)) continue; let j = i; let current = 1; for (let a of primeFactors[j]) { let k = 0; // While the prime factor // divides the number while ((j % a) == 0) { j /= a; k++; if (k > frequecyOfPrimes[a]) { current *= a; } } } // Check element which provides // the maximum product if (current > product) { product = current; ans = i; } } return ans; } function findElement(arr, n, m) { for (let i = 0; i < n; i++) s.add(arr[i]); let frequencyOfPrimes = new Array(10001).fill(0); primeFactorsofLCM(frequencyOfPrimes, arr, n); document.write(elementToBeAdded(frequencyOfPrimes, m) + "<br>"); } // Driver code // Precomputing the prime factors // of all numbers upto 10000 findPrimeFactors(); let N = 5; let M = 9; let arr = [ 2, 5, 3, 8, 1 ]; findElement(arr, N, M); // This code is contributed by _saurabh_jaiswal </script>
7
Complejidad de tiempo: O(N * log N + M * log M)
Publicación traducida automáticamente
Artículo escrito por mohitkumarbt2k18 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA