Dados N números, la tarea es encontrar la eliminación mínima de números tal que el MCD de los números restantes sea mayor que el MCD inicial de N números. Si no es posible aumentar el GCD, escriba “NO”.
Ejemplos:
Entrada: a[] = {1, 2, 4}
Salida: 1
Elimina el primer elemento, luego el nuevo MCD es 2, que es mayor que el MCD inicial, es decir, 1.Entrada: a[] = {6, 9, 15, 30}
Salida: 2
El mcd inicial es 3, quita 6 y 9 para obtener un mcd de 15 que es mayor que 3. También puedes quitar 9 y 15 para obtener un mcd de 6.
Para solucionar el problema anterior se siguen los siguientes pasos:
- Encuentre inicialmente el mcd de N números utilizando algoritmos euclidianos .
- Divide todos los números por el mcd obtenido.
- Usando el método de factorización prima para consultas múltiples, encuentre la factorización prima de cada número en O (log N). El método se puede leer aquí.
- Inserte todos los factores primos en el conjunto para eliminar los duplicados que se obtienen con este método.
- Usando un mapa hash, cuente las frecuencias de los factores primos en cada i-ésimo elemento.
- Una vez que se ha realizado la factorización de números y el conteo se ha almacenado en la tabla de frecuencia, itere en el mapa hash y descubra el factor primo que ocurre la mayor cantidad de veces. No puede ser N, ya que ya hemos dividido los elementos de la array inicialmente por el mcd inicial de N números.
- El número de eliminaciones siempre será n-(hash[prime_factor]) si existen dichos factores después de la división del gcd inicial.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to find the minimum removals
// such that gcd of remaining numbers is more
// than the initial gcd of N numbers
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100001
// stores smallest prime factor for every number
int spf[MAXN];
// Calculating SPF (Smallest Prime Factor) for every
// number till MAXN.
// Time Complexity : O(nloglogn)
void sieve()
{
spf[1] = 1;
for (int i = 2; i < MAXN; i++)
// marking smallest prime factor for every
// number to be itself.
spf[i] = i;
// separately marking spf for every even
// number as 2
for (int i = 4; i < MAXN; i += 2)
spf[i] = 2;
for (int i = 3; i * i < MAXN; i++) {
// checking if i is prime
if (spf[i] == i) {
// marking SPF for all numbers divisible by i
for (int j = i * i; j < MAXN; j += i)
// marking spf[j] if it is not
// previously marked
if (spf[j] == j)
spf[j] = i;
}
}
}
// A O(log n) function returning primefactorization
// by dividing by smallest prime factor at every step
vector<int> getFactorization(int x)
{
vector<int> ret;
while (x != 1) {
ret.push_back(spf[x]);
x = x / spf[x];
}
return ret;
}
// Function which returns the minimal
// removals required to make gcd
// greater than previous
int minimumRemovals(int a[], int n)
{
int g = 0;
// finding initial gcd
for (int i = 0; i < n; i++)
g = __gcd(a[i], g);
unordered_map<int, int> mpp;
// divides all number by initial gcd
for (int i = 0; i < n; i++)
a[i] = a[i] / g;
// iterating for all numbers
for (int i = 0; i < n; i++) {
// prime factorisation to get the prime
// factors of i-th element in the array
vector<int> p = getFactorization(a[i]);
set<int> s;
// insert all the prime factors in
// set to remove duplicates
for (int j = 0; j < p.size(); j++) {
s.insert(p[j]);
}
/// increase the count of prime
// factor in map for every element
for (auto it = s.begin(); it != s.end(); it++) {
int el = *it;
mpp[el] += 1;
}
}
int mini = INT_MAX;
int mini1 = INT_MAX;
// iterate in map and check for every factor
// and its count
for (auto it = mpp.begin(); it != mpp.end(); it++) {
int fir = it->first;
int sec = it->second;
// check for the largest appearing factor
// which does not appears in any one or more
if ((n - sec) <= mini) {
mini = n - sec;
}
}
if (mini != INT_MAX)
return mini;
else
return -1;
}
// Driver code
int main()
{
int a[] = { 6, 9, 15, 30 };
int n = sizeof(a) / sizeof(a[0]);
sieve();
cout << minimumRemovals(a, n);
return 0;
}
Java
// Java program to find the minimum removals
// such that gcd of remaining numbers is more
// than the initial gcd of N numbers
import java.util.*;
class GFG{
static final int MAXN = 100001;
// stores smallest prime factor for every number
static int []spf = new int[MAXN];
// Calculating SPF (Smallest Prime Factor)
// for every number till MAXN.
// Time Complexity : O(nloglogn)
static void sieve()
{
spf[1] = 1;
for(int i = 2; i < MAXN; i++)
// Marking smallest prime factor
// for every number to be itself
spf[i] = i;
// Separately marking spf for every even
// number as 2
for(int i = 4; i < MAXN; i += 2)
spf[i] = 2;
for(int i = 3; i * i < MAXN; i++)
{
// Checking if i is prime
if (spf[i] == i)
{
// Marking SPF for all numbers
// divisible by i
for(int j = i * i; j < MAXN; j += i)
// Marking spf[j] if it is not
// previously marked
if (spf[j] == j)
spf[j] = i;
}
}
}
// A O(log n) function returning primefactorization
// by dividing by smallest prime factor at every step
static Vector<Integer> getFactorization(int x)
{
Vector<Integer> ret = new Vector<>();
while (x != 1)
{
ret.add(spf[x]);
x = x / spf[x];
}
return ret;
}
// Recursive function to return gcd of a and b
static int __gcd(int a, int b)
{
return b == 0 ? a : __gcd(b, a % b);
}
// Function which returns the minimal
// removals required to make gcd
// greater than previous
static int minimumRemovals(int a[], int n)
{
int g = 0;
// Finding initial gcd
for(int i = 0; i < n; i++)
g = __gcd(a[i], g);
HashMap<Integer, Integer> mpp = new HashMap<>();
// Divides all number by initial gcd
for(int i = 0; i < n; i++)
a[i] = a[i] / g;
// Iterating for all numbers
for(int i = 0; i < n; i++)
{
// Prime factorisation to get the prime
// factors of i-th element in the array
Vector<Integer> p = getFactorization(a[i]);
HashSet<Integer> s = new HashSet<>();
// Insert all the prime factors in
// set to remove duplicates
for(int j = 0; j < p.size(); j++)
{
s.add(p.get(j));
}
// Increase the count of prime
// factor in map for every element
for(int it: s)
{
int el = it;
if (mpp.containsKey(el))
{
mpp.put(el, mpp.get(el) + 1);
}
else
{
mpp.put(el, 1);
}
}
}
int mini = Integer.MAX_VALUE;
int mini1 = Integer.MAX_VALUE;
// Iterate in map and check for
// every factor and its count
for(Map.Entry<Integer, Integer> it : mpp.entrySet())
{
int fir = it.getKey();
int sec = it.getValue();
// Check for the largest appearing factor
// which does not appears in any one or more
if ((n - sec) <= mini)
{
mini = n - sec;
}
}
if (mini != Integer.MAX_VALUE)
return mini;
else
return -1;
}
// Driver code
public static void main(String[] args)
{
int a[] = { 6, 9, 15, 30 };
int n = a.length;
sieve();
System.out.print(minimumRemovals(a, n));
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program to find the minimum removals # such that gcd of remaining numbers is more # than the initial gcd of N numbers from math import gcd as __gcd MAXN = 100001 # stores smallest prime factor for every number spf = [i for i in range(MAXN)] # Calculating SPF (Smallest Prime Factor) for every # number till MAXN. # Time Complexity : O(nloglogn) def sieve(): # separately marking spf for every even # number as 2 for i in range(4, MAXN, 2): spf[i] = 2 for i in range(3, MAXN): if i * i > MAXN: break # checking if i is prime if (spf[i] == i): # marking SPF for all numbers divisible by i for j in range(2 * i, MAXN, i): # marking spf[j] if it is not # previously marked if (spf[j] == j): spf[j] = i # A O(log n) function returning primefactorization # by dividing by smallest prime factor at every step def getFactorization(x): ret = [] while (x != 1): ret.append(spf[x]) x = x // spf[x] return ret # Function which returns the minimal # removals required to make gcd # greater than previous def minimumRemovals(a, n): g = 0 # finding initial gcd for i in range(n): g = __gcd(a[i], g) mpp = dict() # divides all number by initial gcd for i in range(n): a[i] = a[i] // g # iterating for all numbers for i in range(n): # prime factorisation to get the prime # factors of i-th element in the array p = getFactorization(a[i]) s = dict() # insert all the prime factors in # set to remove duplicates for j in range(len(p)): s[p[j]] = 1 # increase the count of prime # factor in map for every element for i in s: mpp[i] = mpp.get(i, 0) + 1 mini = 10**9 mini1 = 10**9 # iterate in map and check for every factor # and its count for i in mpp: fir = i sec = mpp[i] # check for the largest appearing factor # which does not appears in any one or more if ((n - sec) <= mini): mini = n - sec if (mini != 10**9): return mini else: return -1 # Driver code a = [6, 9, 15, 30] n = len(a) sieve() print(minimumRemovals(a, n)) # This code is contributed by mohit kumar 29
C#
// C# program to find the minimum
// removals such that gcd of remaining
// numbers is more than the initial
// gcd of N numbers
using System;
using System.Collections.Generic;
class GFG{
static readonly int MAXN = 100001;
// stores smallest prime
// factor for every number
static int []spf =
new int[MAXN];
// Calculating SPF (Smallest
// Prime Factor) for every
// number till MAXN.
// Time Complexity : O(nloglogn)
static void sieve()
{
spf[1] = 1;
for(int i = 2; i < MAXN; i++)
// Marking smallest prime factor
// for every number to be itself
spf[i] = i;
// Separately marking spf for
// every even number as 2
for(int i = 4; i < MAXN; i += 2)
spf[i] = 2;
for(int i = 3; i * i < MAXN; i++)
{
// Checking if i is prime
if (spf[i] == i)
{
// Marking SPF for all numbers
// divisible by i
for(int j = i * i;
j < MAXN; j += i)
// Marking spf[j] if it is
// not previously marked
if (spf[j] == j)
spf[j] = i;
}
}
}
// A O(log n) function returning
// primefactorization by dividing
// by smallest prime factor at
// every step
static List<int> getFactorization(int x)
{
List<int> ret = new List<int>();
while (x != 1)
{
ret.Add(spf[x]);
x = x / spf[x];
}
return ret;
}
// Recursive function to
// return gcd of a and b
static int __gcd(int a,
int b)
{
return b == 0 ? a :
__gcd(b, a % b);
}
// Function which returns the
// minimal removals required
// to make gcd greater than
// previous
static int minimumRemovals(int []a,
int n)
{
int g = 0;
// Finding initial gcd
for(int i = 0; i < n; i++)
g = __gcd(a[i], g);
Dictionary<int,
int> mpp = new Dictionary<int,
int>();
// Divides all number by
// initial gcd
for(int i = 0; i < n; i++)
a[i] = a[i] / g;
// Iterating for all numbers
for(int i = 0; i < n; i++)
{
// Prime factorisation to get the prime
// factors of i-th element in the array
List<int> p = getFactorization(a[i]);
HashSet<int> s = new HashSet<int>();
// Insert all the prime factors in
// set to remove duplicates
for(int j = 0; j < p.Count; j++)
{
s.Add(p[j]);
}
// Increase the count of prime
// factor in map for every
// element
foreach(int it in s)
{
int el = it;
if (mpp.ContainsKey(el))
{
mpp[el]= mpp[el] + 1;
}
else
{
mpp.Add(el, 1);
}
}
}
int mini = int.MaxValue;
int mini1 = int.MaxValue;
// Iterate in map and check for
// every factor and its count
foreach(KeyValuePair<int,
int> it in mpp)
{
int fir = it.Key;
int sec = it.Value;
// Check for the largest appearing
// factor which does not appears
// in any one or more
if ((n - sec) <= mini)
{
mini = n - sec;
}
}
if (mini != int.MaxValue)
return mini;
else
return -1;
}
// Driver code
public static void Main(String[] args)
{
int []a = {6, 9, 15, 30};
int n = a.Length;
sieve();
Console.Write(minimumRemovals(a, n));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to find the minimum removals
// such that gcd of remaining numbers is more
// than the initial gcd of N numbers
let MAXN = 100001;
// stores smallest prime factor for every number
let spf = new Array(MAXN);
// Calculating SPF (Smallest Prime Factor)
// for every number till MAXN.
// Time Complexity : O(nloglogn)
function sieve()
{
spf[1] = 1;
for(let i = 2; i < MAXN; i++)
// Marking smallest prime factor
// for every number to be itself
spf[i] = i;
// Separately marking spf for every even
// number as 2
for(let i = 4; i < MAXN; i += 2)
spf[i] = 2;
for(let i = 3; i * i < MAXN; i++)
{
// Checking if i is prime
if (spf[i] == i)
{
// Marking SPF for all numbers
// divisible by i
for(let j = i * i; j < MAXN; j += i)
// Marking spf[j] if it is not
// previously marked
if (spf[j] == j)
spf[j] = i;
}
}
}
// A O(log n) function returning primefactorization
// by dividing by smallest prime factor at every step
function getFactorization(x)
{
let ret = [];
while (x != 1)
{
ret.push(spf[x]);
x = x / spf[x];
}
return ret;
}
// Recursive function to return gcd of a and b
function __gcd(a,b)
{
return b == 0 ? a : __gcd(b, a % b);
}
// Function which returns the minimal
// removals required to make gcd
// greater than previous
function minimumRemovals(a,n)
{
let g = 0;
// Finding initial gcd
for(let i = 0; i < n; i++)
g = __gcd(a[i], g);
let mpp = new Map();
// Divides all number by initial gcd
for(let i = 0; i < n; i++)
a[i] = a[i] / g;
// Iterating for all numbers
for(let i = 0; i < n; i++)
{
// Prime factorisation to get the prime
// factors of i-th element in the array
let p = getFactorization(a[i]);
let s = new Set();
// Insert all the prime factors in
// set to remove duplicates
for(let j = 0; j < p.length; j++)
{
s.add(p[j]);
}
// Increase the count of prime
// factor in map for every element
for(let it of s.values())
{
let el = it;
if (mpp.has(el))
{
mpp.set(el, mpp.get(el) + 1);
}
else
{
mpp.set(el, 1);
}
}
}
let mini = Number.MAX_VALUE;
let mini1 = Number.MAX_VALUE;
// Iterate in map and check for
// every factor and its count
for(let [key, value] of mpp.entries())
{
let fir = key;
let sec = value;
// Check for the largest appearing factor
// which does not appears in any one or more
if ((n - sec) <= mini)
{
mini = n - sec;
}
}
if (mini != Number.MAX_VALUE)
return mini;
else
return -1;
}
// Driver code
let a = [6, 9, 15, 30];
let n = a.length;
sieve();
document.write(minimumRemovals(a, n));
// This code is contributed by unknown2108
</script>
Producción:
2
Complejidad de tiempo: O(log log N) para precálculo de Sieve y O(N * log N) para cálculo.
Espacio Auxiliar: O(N)