Encuentre un número que divida el máximo de elementos de la array

Posted on by Rudeus Greyrat

Dada una array A[] de N enteros no negativos. Encuentre un número entero mayor que 1, tal que los elementos máximos de la array sean divisibles por él. En caso de igual respuesta imprima la más pequeña.
Ejemplos : 
 

Entrada : A[] = { 2, 4, 5, 10, 8, 15, 16 }; 
Salida : 2 
Explicación : 2 divide [2, 4, 10, 8, 16] ningún otro elemento divide más de 5 números.
Entrada : A[] = { 2, 5, 10 } 
Salida : 2 
Explicación : 2 divide [2, 10] y 5 divide [5, 10], pero 2 es más pequeño. 
 

Enfoque ingenuo: ejecute un bucle for hasta el elemento máximo de la array . Que sea K. Iterar la array y dividir cada elemento de la array por todos los números  1 \leq i \leq K . Actualice el resultado de acuerdo con la cantidad máxima de elementos divididos por el elemento i .
Enfoque eficiente: sabemos que un número puede ser divisible solo por elementos que pueden estar formados por sus factores primos . 
Así encontramos los factores primos de todos los elementos de la array y almacenamos su frecuencia en el hash . Finalmente, devolvemos el elemento con máxima frecuencia entre ellos.
Puedes usar factorización-usando-tamizpara encontrar factores primos en Log(n).
A continuación se muestra la implementación del enfoque anterior: 
 

C++

// CPP program to find a number that
// divides maximum array elements
 
#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) {
        int temp = spf[x];
        ret.push_back(temp);
        while (x % temp == 0)
            x = x / temp;
    }
    return ret;
}
 
// Function to find a number that
// divides maximum array elements
int maxElement(int A[], int n)
{
    // precalculating Smallest Prime Factor
    sieve();
 
    // Hash to store frequency of each divisors
    map<int, int> m;
 
    // Traverse the array and get spf of each element
    for (int i = 0; i < n; ++i) {
 
        // calling getFactorization function
        vector<int> p = getFactorization(A[i]);
 
        for (int i = 0; i < p.size(); i++)
            m[p[i]]++;
    }
 
    int cnt = 0, ans = 1e+7;
 
    for (auto i : m) {
        if (i.second >= cnt) {
            cnt = i.second;
            ans > i.first ? ans = i.first : ans = ans;
        }
    }
 
    return ans;
}
 
// Driver program
int main()
{
    int A[] = { 2, 5, 10 };
    int n = sizeof(A) / sizeof(A[0]);
 
    cout << maxElement(A, n);
 
    return 0;
}

Java

// Java program to find a number that
// divides maximum array elements
import java.util.*;
class Solution
{
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<Integer>();
    while (x != 1) {
        int temp = spf[x];
        ret.add(temp);
        while (x % temp == 0)
            x = x / temp;
    }
    return ret;
}
   
// Function to find a number that
// divides maximum array elements
static int maxElement(int A[], int n)
{
    // precalculating Smallest Prime Factor
    sieve();
   
    // Hash to store frequency of each divisors
    Map<Integer, Integer> m= new HashMap<Integer, Integer>();
   
    // Traverse the array and get spf of each element
    for (int j = 0; j < n; ++j) {
   
        // calling getFactorization function
        Vector<Integer> p = getFactorization(A[j]);
   
        for (int i = 0; i < p.size(); i++)
            m.put(p.get(i),m.get(p.get(i))==null?0:m.get(p.get(i))+1);
    }
   
    int cnt = 0, ans = 10000000;
    // Returns Set view     
       Set< Map.Entry< Integer,Integer> > st = m.entrySet();   
   
       for (Map.Entry< Integer,Integer> me:st)
       {
        if (me.getValue() >= cnt) {
            cnt = me.getValue();
            if(ans > me.getKey())
            ans = me.getKey() ;
            else
            ans = ans;
        }
    }
   
    return ans;
}
   
// Driver program
public static void main(String args[])
{
    int A[] = { 2, 5, 10 };
    int n =A.length;
   
    System.out.print(maxElement(A, n));
   
 
}
}
//contributed by Arnab Kundu

Python3

# Python3 program to find a number that
# divides maximum array elements
import math as mt
 
MAXN = 100001
 
# stores smallest prime factor for
# every number
spf = [0 for i in range(MAXN)]
 
# Calculating SPF (Smallest Prime Factor)
# for every number till MAXN.
# Time Complexity : O(nloglogn)
def sieve():
 
    spf[1] = 1
    for i in range(2, MAXN):
 
        # marking smallest prime factor for
        # every number to be itself.
        spf[i] = i
 
    # separately marking spf for every
    # even number as 2
    for i in range(4, MAXN, 2):
        spf[i] = 2
 
    for i in range(3, mt.ceil(mt.sqrt(MAXN + 1))):
         
        # 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 = list()
    while (x != 1):
        temp = spf[x]
        ret.append(temp)
        while (x % temp == 0):
            x = x //temp
     
    return ret
 
# Function to find a number that
# divides maximum array elements
def maxElement (A, n):
 
    # precalculating Smallest Prime Factor
    sieve()
 
    # Hash to store frequency of each divisors
    m = dict()
 
    # Traverse the array and get spf of each element
    for i in range(n):
 
        # calling getFactorization function
        p = getFactorization(A[i])
 
        for i in range(len(p)):
            if p[i] in m.keys():
                m[p[i]] += 1
            else:
                m[p[i]] = 1
 
    cnt = 0
    ans = 10**9+7
 
    for i in m:
        if (m[i] >= cnt):
            cnt = m[i]
            if ans > i:
                ans = i
            else:
                ans = ans
 
    return ans
 
# Driver Code
A = [2, 5, 10 ]
n = len(A)
 
print(maxElement(A, n))
 
# This code is contributed by Mohit kumar 29

C#

     
// C# program to find a number that
// divides maximum array elements
using System;
using System.Collections.Generic;
 
class Solution
{
     
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)
    {
        int temp = spf[x];
        ret.Add(temp);
        while (x % temp == 0)
            x = x / temp;
    }
    return ret;
}
     
// Function to find a number that
// divides maximum array elements
static int maxElement(int []A, int n)
{
    // precalculating Smallest Prime Factor
    sieve();
     
    // Hash to store frequency of each divisors
    Dictionary<int, int> m= new Dictionary<int, int>();
     
    // Traverse the array and get spf of each element
    for (int j = 0; j < n; ++j)
    {
     
        // calling getFactorization function
        List<int> p = getFactorization(A[j]);
     
        for (int i = 0; i < p.Count; i++)
            if(m.ContainsKey(p[i]))
            m[p[i]] = m[p[i]] + 1;
            else
                m.Add(p[i], 1);
    }
     
    int cnt = 0, ans = 10000000;
     
    // Returns Set view    
    foreach(KeyValuePair<int, int> me in m)
    {
        if (me.Value >= cnt)
        {
            cnt = me.Value;
            if(ans > me.Key)
                ans = me.Key ;
            else
                ans = ans;
        }
    }
     
    return ans;
}
     
// Driver program
public static void Main(String []args)
{
    int []A = { 2, 5, 10 };
    int n =A.Length;
     
    Console.Write(maxElement(A, n));
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// JavaScript program to find a number that
// divides maximum array elements
 
let MAXN=100001;
 
// stores smallest prime factor for every number
let spf= new Array(MAXN);
for(let i=0;i<MAXN;i++)
{
    spf[i]=0;
}
 
// 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) {
        let temp = spf[x];
        ret.push(temp);
        while (x % temp == 0)
            x = Math.floor(x / temp);
    }
    return ret;
}
 
// Function to find a number that
// divides maximum array elements
function maxElement(A,n)
{
    // precalculating Smallest Prime Factor
    sieve();
     
    // Hash to store frequency of each divisors
    let m= new Map();
     
    // Traverse the array and get spf of each element
    for (let j = 0; j < n; ++j) {
     
        // calling getFactorization function
        let p = getFactorization(A[j]);
     
        for (let i = 0; i < p.length; i++)
            m.set(p[i],m.get(p[i])==null?0:m.get(p[i])+1);
    }
     
    let cnt = 0, ans = 10000000;
    // Returns Set view     
           
     
       for (let [key, value] of m.entries())
       {
        if (value >= cnt) {
            cnt = value;
            if(ans > key)
                ans = key ;
            else
                ans = ans;
        }
    }
     
    return ans;
}
 
// Driver program
let A=[ 2, 5, 10];
let n =A.length;
document.write(maxElement(A, n));
 
     
 
// This code is contributed by patel2127
 
</script>
Producción: 

2

 

Complejidad de tiempo: O(N*log(N))
 

Publicación traducida automáticamente

Artículo escrito por Sanjit_Prasad y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *