Dada una array arr[] de N enteros, la tarea es encontrar el número más pequeño que divide la cantidad mínima de elementos de la array.
Ejemplos:
Entrada: arr[] = {2, 12, 6}
Salida: 5
Aquí, 1 divide 3 elementos
2 divide 3 elementos
3 divide 2 elementos
4 divide 1 elemento
5 divide ningún elemento
6 divide 2 elementos
7 divide ningún elemento
8 divide ningún elemento
9 no divide ningún elemento
10 no divide ningún elemento
11 no divide ningún elemento
12 divide 1 elemento
5 es el número más pequeño que no divide ningún
número en la array. Por lo tanto, ans = 5
Entrada: arr[] = {1, 7, 9}
Salida: 2
Planteamiento: Observemos primero algunos detalles. Ya existe un número que divide cero elementos, es decir, max(arr) + 1 . Ahora, solo necesitamos encontrar el número mínimo que divide cero números en la array.
En este artículo, se discutirá un enfoque para resolver este problema en O(M*log(M) + N) usando un tamiz (M = max(arr)).
- Primero, encuentre el elemento máximo, M , en la array y cree una tabla de frecuencia freq[] de longitud M + 1 para almacenar la frecuencia de los números entre 1 y M .
- Itere la array y actualice freq[] como freq[arr[i]]++ para cada índice i .
- Ahora, aplica el algoritmo tamiz. Iterar entre todos los elementos entre 1 y M + 1 .
- Digamos que estamos iterando por un número X.
- Cree una variable temporal cnt .
- Para cada múltiplo de X entre X y M {X, 2X, 3X….} actualice cnt como cnt = cnt + freq[kX] .
- Si cnt = 0 , la respuesta será X ; de lo contrario, continúe iterando para el siguiente valor de X.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the smallest number
// that divides minimum number of elements
// in the given array
int findMin(int* arr, int n)
{
// m stores the maximum in the array
int m = 0;
for (int i = 0; i < n; i++)
m = max(m, arr[i]);
// Frequency array
int freq[m + 2] = { 0 };
for (int i = 0; i < n; i++)
freq[arr[i]]++;
// Sieve
for (int i = 1; i <= m + 1; i++) {
int j = i;
int cnt = 0;
// Incrementing j
while (j <= m) {
cnt += freq[j];
j += i;
}
// If no multiples of j are
// in the array
if (!cnt)
return i;
}
return m + 1;
}
// Driver code
int main()
{
int arr[] = { 2, 12, 6 };
int n = sizeof(arr) / sizeof(int);
cout << findMin(arr, n);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to return the smallest number
// that divides minimum number of elements
// in the given array
static int findMin(int arr[], int n)
{
// m stores the maximum in the array
int m = 0;
for (int i = 0; i < n; i++)
m = Math.max(m, arr[i]);
// Frequency array
int freq [] = new int[m + 2];
for (int i = 0; i < n; i++)
freq[arr[i]]++;
// Sieve
for (int i = 1; i <= m + 1; i++)
{
int j = i;
int cnt = 0;
// Incrementing j
while (j <= m)
{
cnt += freq[j];
j += i;
}
// If no multiples of j are
// in the array
if (cnt == 0)
return i;
}
return m + 1;
}
// Driver code
public static void main (String[] args)
{
int arr[] = { 2, 12, 6 };
int n = arr.length;
System.out.println(findMin(arr, n));
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 implementation of the approach # Function to return the smallest number # that divides minimum number of elements # in the given array def findMin(arr, n): # m stores the maximum in the array m = 0 for i in range(n): m = max(m, arr[i]) # Frequency array freq = [0] * (m + 2) for i in range(n): freq[arr[i]] += 1 # Sieve for i in range(1, m + 2): j = i cnt = 0 # Incrementing j while (j <= m): cnt += freq[j] j += i # If no multiples of j are # in the array if (not cnt): return i return m + 1 # Driver code arr = [2, 12, 6] n = len(arr) print(findMin(arr, n)) # This code is contributed by Mohit Kumar
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the smallest number
// that divides minimum number of elements
// in the given array
static int findMin(int []arr, int n)
{
// m stores the maximum in the array
int m = 0;
for (int i = 0; i < n; i++)
m = Math.Max(m, arr[i]);
// Frequency array
int []freq = new int[m + 2];
for (int i = 0; i < n; i++)
freq[arr[i]]++;
// Sieve
for (int i = 1; i <= m + 1; i++)
{
int j = i;
int cnt = 0;
// Incrementing j
while (j <= m)
{
cnt += freq[j];
j += i;
}
// If no multiples of j are
// in the array
if (cnt == 0)
return i;
}
return m + 1;
}
// Driver code
public static void Main ()
{
int []arr = { 2, 12, 6 };
int n = arr.Length;
Console.WriteLine(findMin(arr, n));
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// Javascript implementation of the approach
// Function to return the smallest number
// that divides minimum number of elements
// in the given array
function findMin(arr, n)
{
// m stores the maximum in the array
var m = 0;
for (var i = 0; i < n; i++)
m = Math.max(m, arr[i]);
// Frequency array
var freq = Array(m+2).fill(0);
for (var i = 0; i < n; i++)
freq[arr[i]]++;
// Sieve
for (var i = 1; i <= m + 1; i++) {
var j = i;
var cnt = 0;
// Incrementing j
while (j <= m) {
cnt += freq[j];
j += i;
}
// If no multiples of j are
// in the array
if (!cnt)
return i;
}
return m + 1;
}
// Driver code
var arr = [2, 12, 6];
var n = arr.length;
document.write( findMin(arr, n));
</script>
Producción:
5
Complejidad temporal: O(Mlog(M) + N)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por DivyanshuShekhar1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA