Dada una array arr[] de enteros, la tarea es encontrar el elemento (que no sea 1) que sea el factor del número máximo de elementos de la array. Si existen múltiples factores de este tipo, imprima todos los factores en orden ascendente.
Ejemplos:
Entrada: arr[] = {10, 20}
Salida: 2 5 10
Los factores de 10 son 1, 2, 5, 10.
Los factores de 20 son 1, 2, 4, 5, 10, 20.
Los factores distintos de 1, que ocurren la mayoría de las veces (dos veces) son 2, 5, 10.Entrada: arr[] = {120, 15, 24, 63, 18}
Salida: 3
Acercarse:
- Inicialice dos listas, una para almacenar el rango (el número de elementos de los que el número entero es un factor) del factor y otra para almacenar el factor.
- Comience desde 2 hasta el elemento máximo de la array.
- Cuente el número de elementos en la array. El entero actual es un factor de.
- Agregue el conteo a la lista de clasificación y los números enteros a la lista de factores.
- Encuentre el número entero con el rango máximo.
- Imprime todos los elementos con el mismo rango.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP implementation of the approach
#include<bits/stdc++.h>
using namespace std;
// Function to print the integers that divide
// the maximum number of elements from the array
void maximumFactor(vector<int>arr)
{
// Initialize two lists
// to store rank and factors
int n = arr.size();
vector<int> rank;
vector<int> factors;
int max = *max_element(arr.begin(), arr.end());
// Start from 2 till the maximum element in arr
for (int i = 2; i <= max; i++)
{
// Initialize a variable
// to count the number of elements
// it is a factor of
int count = 0;
for (int j = 0; j < n; j++)
{
if (arr[j] % i == 0)
count+= 1;
rank.push_back(count);
factors.push_back(i);
}
}
// Maximum rank in the rank list
int m = *max_element(rank.begin(),rank.end());
for (int i = 0; i < rank.size(); i++)
{
// Print all the elements with rank m
if (rank[i] == m)
cout << factors[i] <<" ";
}
}
// Driver code
int main()
{
vector<int>arr = {120, 15, 24, 63, 18};
maximumFactor(arr);
}
// This code is contributed by
// Surendra_Gangwar
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Function to print the integers that
// divide the maximum number of
// elements from the array
static void maximumFactor(int []arr)
{
// Initialize two lists to store
// rank and factors
int[] rank = new int[Arrays.stream(arr).max().getAsInt() + 1];
int[] factors = new int[Arrays.stream(arr).max().getAsInt() + 1];
int g = 0;
// Start from 2 till the maximum
// element in arr
for (int i = 2;
i <= Arrays.stream(arr).max().getAsInt(); i++)
{
// Initialize a variable to count
// the number of elements it is a
// factor of
int count = 0;
for (int j = 0; j < arr.length; j++)
if (arr[j] % i == 0)
count += 1;
rank[g] = count;
factors[g] = i;
g++;
}
// Maximum rank in the rank list
int m = Arrays.stream(rank).max().getAsInt();
for (int i = 0; i < rank.length; i++)
{
// Print all the elements with rank m
if (rank[i] == m)
System.out.print(factors[i] + " ");
}
}
// Driver code
public static void main (String[] args)
{
int []arr = {120, 15, 24, 63, 18};
maximumFactor(arr);
}
}
// This code is contributed by
// chandan_jnu
Python
# Python3 implementation of the approach # Function to print the integers that divide # the maximum number of elements from the array def maximumFactor(arr): # Initialize two lists # to store rank and factors rank, factors = [], [] # Start from 2 till the maximum element in arr for i in range(2, max(arr)+1): # Initialize a variable # to count the number of elements # it is a factor of count = 0 for j in arr: if j % i == 0:count+= 1 rank.append(count) factors.append(i) # Maximum rank in the rank list m = max(rank) for i in range(len(rank)): # Print all the elements with rank m if rank[i]== m: print(factors[i], end =" ") # Driver code arr = [120, 15, 24, 63, 18] maximumFactor(arr)
C#
// C# implementation of the approach
using System;
using System.Collections;
using System.Linq;
class GFG
{
// Function to print the integers that
// divide the maximum number of
// elements from the array
static void maximumFactor(int []arr)
{
// Initialize two lists to store
// rank and factors
int[] rank = new int[arr.Max() + 1];
int[] factors = new int[arr.Max() + 1];
int g = 0;
// Start from 2 till the maximum
// element in arr
for (int i = 2; i <= arr.Max(); i++)
{
// Initialize a variable to count
// the number of elements it is a
// factor of
int count = 0 ;
for (int j = 0; j < arr.Length; j++)
if (arr[j] % i == 0)
count += 1;
rank[g]=count;
factors[g]=i;
g++;
}
// Maximum rank in the rank list
int m = rank.Max();
for (int i = 0; i < rank.Length; i++)
{
// Print all the elements with rank m
if ((int)rank[i] == m)
Console.Write(factors[i]+" ");
}
}
// Driver code
static void Main()
{
int []arr = {120, 15, 24, 63, 18};
maximumFactor(arr);
}
}
// This code is contributed by chandan_jnu
PHP
<?php
// PHP implementation of the approach
// Function to print the integers that
// divide the maximum number of
// elements from the array
function maximumFactor($arr)
{
// Initialize two lists to store
// rank and factors
$rank = array();
$factors = array();
// Start from 2 till the maximum
// element in arr
for ($i = 2; $i <= max($arr); $i++)
{
// Initialize a variable to count
// the number of elements it is a
// factor of
$count = 0 ;
for ($j = 0; $j < sizeof($arr); $j++)
if ($arr[$j] % $i == 0)
$count += 1;
array_push($rank, $count);
array_push($factors, $i);
}
// Maximum rank in the rank list
$m = max($rank);
for ($i = 0; $i < sizeof($rank); $i++)
{
// Print all the elements with rank m
if ($rank[$i] == $m)
echo $factors[$i], " ";
}
}
// Driver code
$arr = array(120, 15, 24, 63, 18);
maximumFactor($arr)
// This code is contributed by Ryuga
?>
Javascript
<script>
// Javascript implementation of the approach
// Function to print the integers that divide
// the maximum number of elements from the array
function maximumFactor(arr)
{
// Initialize two lists
// to store rank and factors
var n = arr.length;
var rank = [];
var factors = [];
var max = arr.reduce((a,b)=> Math.max(a,b));
// Start from 2 till the maximum element in arr
for (var i = 2; i <= max; i++)
{
// Initialize a variable
// to count the number of elements
// it is a factor of
var count = 0;
for (var j = 0; j < n; j++)
{
if (arr[j] % i == 0)
count+= 1;
rank.push(count);
factors.push(i);
}
}
// Maximum rank in the rank list
var m = rank.reduce((a,b)=>Math.max(a,b));
for (var i = 0; i < rank.length; i++)
{
// Print all the elements with rank m
if (rank[i] == m)
document.write( factors[i] + " ");
}
}
// Driver code
var arr = [120, 15, 24, 63, 18];
maximumFactor(arr);
</script>
Producción:
3
Complejidad de tiempo: O(n * max(arr)), donde max(arr) es el elemento más grande de la array arr.
Espacio Auxiliar: O(n * max(arr))