Dada una array arr[] que consta de N enteros positivos, la tarea es determinar el entero positivo más pequeño K tal que ninguno de los elementos de la array sea divisible por K . Si no hay tal entero
Ejemplos:
Entrada: arr[] = {3, 2, 6, 9, 2}
Salida: 4
Explicación: Ninguno de los elementos de la array es divisible por 4 (el menor positivo).Entrada: arr[] = {3, 5, 1, 19, 11}
Salida: 2
Enfoque: siga los pasos a continuación para resolver el problema:
- Encuentre el elemento máximo de la array dada , digamos maxE .
- Itere sobre el rango [1, maxE + 1] usando la variable i y verifique si hay un número entero en la array dada que sea divisible por i o no. Si se encuentra que es cierto, entonces verifique el siguiente entero en este rango.
- De lo contrario, imprima el número actual i .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <iostream>
using namespace std;
// Function to find the smallest number
// which doesn't divides any integer in
// the given array arr[]
void smallestNumber(int arr[], int len)
{
int maxi = 0;
// Traverse the array arr[]
for (int i = 0; i < len; i++) {
// Maximum array element
maxi = std::max(maxi, arr[i]);
}
// Initialize variable
int ans = -1;
// Traverse from 2 to max
for (int i = 2; i < maxi + 2; i++) {
// Stores if any such
// integer is found or not
bool flag = true;
for (int j = 0; j < len; j++) {
// If any array element
// is divisible by j
if (arr[j] % i == 0) {
flag = false;
break;
}
}
if (flag) {
// Smallest integer
ans = i;
break;
}
}
// Print the answer
cout << ans;
}
// Driver Code
int main()
{
int arr[] = { 3, 2, 6, 9, 2 };
int N = sizeof(arr)
/ sizeof(arr[0]);
// Function Call
smallestNumber(arr, N);
return 0;
}
Java
// Java program for the above approach
class GFG
{
// Function to find the smallest number
// which doesn't divides any integer in
// the given array arr[]
static void smallestNumber(int arr[], int len)
{
int maxi = 0;
// Traverse the array arr[]
for (int i = 0; i < len; i++)
{
// Maximum array element
maxi = Math.max(maxi, arr[i]);
}
// Initialize variable
int ans = -1;
// Traverse from 2 to max
for (int i = 2; i < maxi + 2; i++)
{
// Stores if any such
// integer is found or not
boolean flag = true;
for (int j = 0; j < len; j++)
{
// If any array element
// is divisible by j
if (arr[j] % i == 0)
{
flag = false;
break;
}
}
if (flag)
{
// Smallest integer
ans = i;
break;
}
}
// Print the answer
System.out.print(ans);
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 3, 2, 6, 9, 2 };
int N = arr.length;
// Function Call
smallestNumber(arr, N);
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 program for the above approach # Function to find the smallest number # which doesn't divides any integer in # the given array arr[] def smallestNumber(arr, lenn): maxi = 0 # Traverse the array arr[] for i in range(lenn): # Maximum array element maxi = max(maxi, arr[i]) # Initialize variable ans = -1 # Traverse from 2 to max for i in range(2, maxi + 2): # Stores if any such # integer is found or not flag = True for j in range(lenn): # If any array element # is divisible by j if (arr[j] % i == 0): flag = False break if (flag): # Smallest integer ans = i break # Print the answer print (ans) # Driver Code if __name__ == '__main__': arr = [3, 2, 6, 9, 2] N = len(arr) #Function Call smallestNumber(arr, N) # This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
public class GFG
{
// Function to find the smallest number
// which doesn't divides any integer in
// the given array arr[]
static void smallestNumber(int []arr, int len)
{
int maxi = 0;
// Traverse the array arr[]
for (int i = 0; i < len; i++)
{
// Maximum array element
maxi = Math.Max(maxi, arr[i]);
}
// Initialize variable
int ans = -1;
// Traverse from 2 to max
for (int i = 2; i < maxi + 2; i++)
{
// Stores if any such
// integer is found or not
bool flag = true;
for (int j = 0; j < len; j++)
{
// If any array element
// is divisible by j
if (arr[j] % i == 0)
{
flag = false;
break;
}
}
if (flag)
{
// Smallest integer
ans = i;
break;
}
}
// Print the answer
Console.WriteLine(ans);
}
// Driver Code
public static void Main(string[] args)
{
int []arr = { 3, 2, 6, 9, 2 };
int N = arr.Length;
// Function Call
smallestNumber(arr, N);
}
}
// This code is contributed by AnkThon
Javascript
<script>
// javascript program of the above approach
// Function to find the smallest number
// which doesn't divides any integer in
// the given array arr[]
function smallestNumber(arr, len)
{
let maxi = 0;
// Traverse the array arr[]
for (let i = 0; i < len; i++)
{
// Maximum array element
maxi = Math.max(maxi, arr[i]);
}
// Initialize variable
let ans = -1;
// Traverse from 2 to max
for (let i = 2; i < maxi + 2; i++)
{
// Stores if any such
// integer is found or not
let flag = true;
for (let j = 0; j < len; j++)
{
// If any array element
// is divisible by j
if (arr[j] % i == 0)
{
flag = false;
break;
}
}
if (flag)
{
// Smallest integer
ans = i;
break;
}
}
// Print the answer
document.write(ans);
}
// Driver Code
let arr = [ 3, 2, 6, 9, 2 ];
let N = arr.length;
// Function Call
smallestNumber(arr, N);
</script>
Producción:
4
Complejidad de tiempo: O(N*max) donde max es el elemento máximo en la array dada
Espacio auxiliar: O(N)