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 utilizando la factorización de raíces cuadradas. Cada elemento se factorizará y se mantendrá una array de frecuencias cnt[] de longitud max(arr) + 2 para almacenar el recuento de una cantidad de elementos en la array, para cada elemento entre 1 y max(arr) + 1 .
- Para cada i , factorice arr[i] .
- Para cada factor Fij de arr[i] , actualice cnt[Fij] como cnt[Fij]++ .
- Encuentre el número más pequeño k en la array de frecuencias cnt[] con cnt[k] = 0 .
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
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 table
int cnt[m + 2] = { 0 };
// Loop to factorize
for (int i = 0; i < n; i++) {
// sqrt factorization of the numbers
for (int j = 1; j * j <= arr[i]; j++) {
if (arr[i] % j == 0) {
if (j * j == arr[i])
cnt[j]++;
else
cnt[j]++, cnt[arr[i] / j]++;
}
}
}
// Finding the smallest number
// with zero multiples
for (int i = 1; i <= m + 1; i++)
if (cnt[i] == 0) {
return i;
}
return -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
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 table
int cnt[] = new int[m + 2];
// Loop to factorize
for (int i = 0; i < n; i++)
{
// sqrt factorization of the numbers
for (int j = 1; j * j <= arr[i]; j++)
{
if (arr[i] % j == 0)
{
if (j * j == arr[i])
cnt[j]++;
else
{
cnt[j]++;
cnt[arr[i] / j]++;
}
}
}
}
// Finding the smallest number
// with zero multiples
for (int i = 1; i <= m + 1; i++)
if (cnt[i] == 0)
{
return i;
}
return -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 def findMin(arr, n): # m stores the maximum in the array m = 0 for i in range(n): m = max(m, arr[i]) # Frequency table cnt = [0] * (m + 2) # Loop to factorize for i in range(n): # sqrt factorization of the numbers j = 1 while j * j <= arr[i]: if (arr[i] % j == 0): if (j * j == arr[i]): cnt[j] += 1 else: cnt[j] += 1 cnt[arr[i] // j] += 1 j += 1 # Finding the smallest number # with zero multiples for i in range(1, m + 2): if (cnt[i] == 0): return i return -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
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 table
int []cnt = new int[m + 2];
// Loop to factorize
for (int i = 0; i < n; i++)
{
// sqrt factorization of the numbers
for (int j = 1; j * j <= arr[i]; j++)
{
if (arr[i] % j == 0)
{
if (j * j == arr[i])
cnt[j]++;
else
{
cnt[j]++;
cnt[arr[i] / j]++;
}
}
}
}
// Finding the smallest number
// with zero multiples
for (int i = 1; i <= m + 1; i++)
if (cnt[i] == 0)
{
return i;
}
return -1;
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 2, 12, 6 };
int n = arr.Length;
Console.WriteLine(findMin(arr, n));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript implementation of the approach
// Function to return the smallest number
// that divides minimum number of elements
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 table
var cnt = Array(m+2).fill(0);
// Loop to factorize
for (var i = 0; i < n; i++) {
// sqrt factorization of the numbers
for (var j = 1; j * j <= arr[i]; j++) {
if (arr[i] % j == 0) {
if (j * j == arr[i])
cnt[j]++;
else
cnt[j]++, cnt[arr[i] / j]++;
}
}
}
// Finding the smallest number
// with zero multiples
for (var i = 1; i <= m + 1; i++)
if (cnt[i] == 0) {
return i;
}
return -1;
}
// Driver code
var arr = [2, 12, 6];
var n = arr.length;
document.write( findMin(arr, n));
</script>
5
Complejidad de tiempo: O(N * sqrt(max(arr))).
Espacio auxiliar: O(max(arr))
Publicación traducida automáticamente
Artículo escrito por DivyanshuShekhar1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA