Dada una array de N números, la tarea es imprimir todos los números mayores que 1 que dividen el máximo de elementos de la array.
Ejemplos :
Entrada : a[] = {6, 6, 12, 18, 13}
Salida : 2 3 6
Todos los números dividen el máximo de elementos de array, es decir, 4
Entrada : a[] = {12, 15, 27, 20, 40 }
Salida : 2 3 4 5
Acercarse:
- Utilice hashing para almacenar el recuento de todos los factores de cada elemento de la array. Podemos encontrar todos los factores de número en O(sqrt N).
- Recorra todos los factores y encuentre el recuento de elementos de array máximos que se dividen por números.
- Vuelva a recorrer todos los factores e imprima los factores que ocurren la mayor cantidad de veces.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to print all the numbers
// that divides maximum of array elements
#include <bits/stdc++.h>
using namespace std;
// Function that prints all the numbers
// which divides maximum of array elements
void printNumbers(int a[], int n)
{
// hash to store the number of times
// a factor is there
unordered_map<int, int> mpp;
for (int i = 0; i < n; i++) {
int num = a[i];
// find all the factors
for (int j = 1; j * j <= num; j++) {
// if j is factor of num
if (num % j == 0) {
if (j != 1)
mpp[j]++;
if ((num / j) != j)
mpp[num / j]++;
}
}
}
// find the maximum times
// it can divide
int maxi = 0;
for (auto it : mpp) {
maxi = max(it.second, maxi);
}
// print all the factors of
// numbers which divides the
// maximum array elements
for (auto it : mpp) {
if (it.second == maxi)
cout << it.first << " ";
}
}
// Driver Code
int main()
{
int a[] = { 12, 15, 27, 20, 40 };
int n = sizeof(a) / sizeof(a[0]);
printNumbers(a, n);
}
Java
// Java program to print all the numbers
// that divides maximum of array elements
import java.util.*;
class GFG
{
// Function that prints all the numbers
// which divides maximum of array elements
static void printNumbers(int a[], int n)
{
// hash to store the number of times
// a factor is there
Map<Integer,
Integer> mpp = new HashMap<>();
for (int i = 0; i < n; i++)
{
int num = a[i];
// find all the factors
for (int j = 1; j * j <= num; j++)
{
// if j is factor of num
if (num % j == 0)
{
if (j != 1)
{
if(mpp.containsKey(j))
{
mpp.put(j, mpp.get(j) + 1);
}
else
{
mpp.put(j, 1);
}
}
if ((num / j) != j)
{
if(mpp.containsKey(num / j))
{
mpp.put(num / j, mpp.get(num / j) + 1);
}
else
{
mpp.put(num / j, 1);
}
}
}
}
}
// find the maximum times
// it can divide
int maxi = 0;
for (Map.Entry<Integer,
Integer> it : mpp.entrySet())
{
maxi = Math.max(it.getValue(), maxi);
}
// print all the factors of
// numbers which divides the
// maximum array elements
for (Map.Entry<Integer,
Integer> it : mpp.entrySet())
{
if (it.getValue() == maxi)
System.out.print(it.getKey() + " ");
}
}
// Driver Code
public static void main(String[] args)
{
int a[] = { 12, 15, 27, 20, 40 };
int n = a.length;
printNumbers(a, n);
}
}
// This code is contributed by Princi Singh
Python3
# Python3 program to print all the numbers # that divides maximum of array elements # Function that prints all the numbers # which divides maximum of array elements def printNumbers(a, n): # hash to store the number of times # a factor is there mpp = dict() for i in range(n): num = a[i] # find all the factors for j in range(1, num + 1): if j * j > num: break # if j is factor of num if (num % j == 0): if (j != 1): mpp[j]=mpp.get(j, 0) + 1 if ((num // j) != j): mpp[num // j]=mpp.get(num//j, 0) + 1 # find the maximum times # it can divide maxi = 0 for it in mpp: maxi = max(mpp[it], maxi) # print all the factors of # numbers which divides the # maximum array elements for it in mpp: if (mpp[it] == maxi): print(it,end=" ") # Driver Code a = [12, 15, 27, 20, 40 ] n = len(a) printNumbers(a, n) # This code is contributed by mohit kumar
C#
// C# program to print all the numbers
// that divides maximum of array elements
using System;
using System.Collections.Generic;
class GFG
{
// Function that prints all the numbers
// which divides maximum of array elements
static void printNumbers(int []a, int n)
{
// hash to store the number of times
// a factor is there
Dictionary<int,int> mpp = new Dictionary<int,int>();
for (int i = 0; i < n; i++)
{
int num = a[i];
// find all the factors
for (int j = 1; j * j <= num; j++)
{
// if j is factor of num
if (num % j == 0)
{
if (j != 1)
{
if(mpp.ContainsKey(j))
{
var v = mpp[j];
mpp.Remove(j);
mpp.Add(j, v + 1);
}
else
{
mpp.Add(j, 1);
}
}
if ((num / j) != j)
{
if(mpp.ContainsKey(num / j))
{
var v = mpp[num/j];
mpp.Remove(num/j);
mpp.Add(num / j, v + 1);
}
else
{
mpp.Add(num / j, 1);
}
}
}
}
}
// find the maximum times
// it can divide
int maxi = 0;
foreach(KeyValuePair<int, int> it in mpp)
{
maxi = Math.Max(it.Value, maxi);
}
// print all the factors of
// numbers which divides the
// maximum array elements
foreach(KeyValuePair<int, int> it in mpp)
{
if (it.Value == maxi)
Console.Write(it.Key + " ");
}
}
// Driver Code
public static void Main(String[] args)
{
int []a = { 12, 15, 27, 20, 40 };
int n = a.Length;
printNumbers(a, n);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to print all the numbers
// that divides maximum of array elements
// Function that prints all the numbers
// which divides maximum of array elements
function printNumbers(a, n)
{
// hash to store the number of times
// a factor is there
var mpp = new Map();
for (var i = 0; i < n; i++) {
var num = a[i];
// find all the factors
for (var j = 1; j * j <= num; j++) {
// if j is factor of num
if (num % j == 0) {
if (j != 1)
{
if(mpp.has(j))
mpp.set(j, mpp.get(j)+1)
else
mpp.set(j, 1)
}
if ((num / j) != j)
{
if(mpp.has(parseInt(num / j)))
mpp.set(parseInt(num / j),
mpp.get(parseInt(num / j))+1)
else
mpp.set(parseInt(num / j), 1)
}
}
}
}
// find the maximum times
// it can divide
var maxi = 0;
mpp.forEach((value, key) => {
maxi = Math.max(value, maxi);
});
// print all the factors of
// numbers which divides the
// maximum array elements
mpp.forEach((value,key) => {
if (value == maxi)
{
document.write(key+ " ");
}
});
}
// Driver Code
var a = [12, 15, 27, 20, 40];
var n = a.length;
printNumbers(a, n);
</script>
Producción:
5 2 3 4
Complejidad de tiempo: O(N * sqrt ( max (elemento de array))), ya que estamos usando bucles anidados donde el bucle exterior atraviesa N veces y en el bucle interior la condición es j*j<=num, raíz cuadrada en ambos lados tendremos j<=sqrt(num), por lo que el ciclo interno atraviesa sqrt (num) veces. Donde N es el número de elementos de la array y num es el elemento máximo de la array.
Espacio auxiliar: O(N * sqrt(max(array element))), ya que estamos usando espacio adicional para el mapa.