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>
Producción:
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