Dada una array arr[] que consta de N enteros positivos y enteros L y R , la tarea es encontrar el recuento de números en el rango [L, R] que no son divisibles por ninguno de los elementos de la array.
Ejemplos:
Entrada: arr[] = {2, 3, 4, 5, 6}, L = 1, R = 20
Salida: 6
Explicación:
Los 6 números en el rango [1, 20] que no son divisibles por ninguno de la array los elementos son 1, 7, 11, 13, 17 y 19.Entrada: arr[] = {1, 2, 3}, L = 75, R = 1000000
Salida: 0
Explicación:
Dado que todos los números son divisibles por 1, la respuesta es 0.
Enfoque ingenuo: el enfoque simple es iterar a través de todos los números en el rango dado [L, R] , y para cada número, verificar si es divisible por alguno de los elementos de la array. Si no es divisible por ninguno de los elementos de la array, incremente el conteo. Después de verificar todos los números, imprima el conteo.
Complejidad de tiempo: O((R – L + 1)*N)
Espacio auxiliar: O(N)
Enfoque eficiente: el enfoque anterior se puede optimizar utilizando Sieve of Eratosthenes , marcando todos los múltiplos de un número y almacenándolos en una estructura de datos eficiente, digamos Set , que proporciona una operación de búsqueda en un tiempo casi constante. Siga los pasos a continuación para resolver el problema:
- Primero, para cada elemento de la array, digamos arr[i] , almacene todos sus múltiplos, más pequeños que R , en un Conjunto usando Sieve of Eratosthenes .
- El número de enteros en el rango [1, R] que no son divisibles por ningún número presente en la array dada será igual a (R – tamaño del conjunto) . Que sea A.
- De manera similar, encuentre los números en el rango [1, L] que no son divisibles por ningún número presente en la array dada. Que sea B.
- Después de los pasos anteriores, imprima el valor de (A – B) como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the non-multiples
// till k
int findNonMultiples(int arr[],
int n, int k)
{
// Stores all unique multiples
set<int> multiples;
// Iterate the array
for (int i = 0; i < n; ++i) {
// For finding duplicates
// only once
if (multiples.find(arr[i])
== multiples.end()) {
// Inserting all multiples
// into the set
for (int j = 1;
j <= k / arr[i]; j++) {
multiples.insert(arr[i] * j);
}
}
}
// Returning only the count of
// numbers that are not divisible
// by any of the array elements
return k - multiples.size();
}
// Function to count the total values
// in the range [L, R]
int countValues(int arr[], int N,
int L, int R)
{
// Count all values in the range
// using exclusion principle
return findNonMultiples(arr, N, R)
- findNonMultiples(arr, N, L - 1);
}
// Driver Code
int main()
{
int arr[] = { 2, 3, 4, 5, 6 };
int N = sizeof(arr) / sizeof(arr[0]);
int L = 1, R = 20;
// Function Call
cout << countValues(arr, N, L, R);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG{
// Function to find the non-multiples
// till k
public static int findNonMultiples(int[] arr, int n,
int k)
{
// Stores all unique multiples
Set<Integer> multiples = new HashSet<Integer>();
// Iterate the array
for(int i = 0; i < n; ++i)
{
// For finding duplicates
// only once
if (!multiples.contains(arr[i]))
{
// Inserting all multiples
// into the set
for(int j = 1; j <= k / arr[i]; j++)
{
multiples.add(arr[i] * j);
}
}
}
// Returning only the count of
// numbers that are not divisible
// by any of the array elements
return k - multiples.size();
}
// Function to count the total values
// in the range [L, R]
public static int countValues(int[] arr, int N,
int L, int R)
{
// Count all values in the range
// using exclusion principle
return findNonMultiples(arr, N, R) -
findNonMultiples(arr, N, L - 1);
}
// Driver code
public static void main(String[] args)
{
int[] arr = { 2, 3, 4, 5, 6 };
int N = arr.length;
int L = 1;
int R = 20;
// Function Call
System.out.println(countValues(arr, N, L, R));
}
}
// This code is contributed by rohitsingh07052
Python3
# Python3 program for the above approach # Function to find the non-multiples # till k def findNonMultiples(arr, n, k): # Stores all unique multiples multiples = set([]) # Iterate the array for i in range(n): # For finding duplicates # only once if (arr[i] not in multiples): # Inserting all multiples # into the set for j in range(1, k // arr[i] + 1): multiples.add(arr[i] * j) # Returning only the count of # numbers that are not divisible # by any of the array elements return k - len(multiples) # Function to count the total values # in the range [L, R] def countValues(arr, N, L, R): # Count all values in the range # using exclusion principle return (findNonMultiples(arr, N, R) - findNonMultiples(arr, N, L - 1)) # Driver Code if __name__ == "__main__": arr = [ 2, 3, 4, 5, 6 ] N = len(arr) L = 1 R = 20 # Function Call print( countValues(arr, N, L, R)) # This code is contributed by chitranayal
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to find the non-multiples
// till k
public static int findNonMultiples(int[] arr, int n,
int k)
{
// Stores all unique multiples
HashSet<int> multiples = new HashSet<int>();
// Iterate the array
for(int i = 0; i < n; ++i)
{
// For finding duplicates
// only once
if (!multiples.Contains(arr[i]))
{
// Inserting all multiples
// into the set
for(int j = 1; j <= k / arr[i]; j++)
{
multiples.Add(arr[i] * j);
}
}
}
// Returning only the count of
// numbers that are not divisible
// by any of the array elements
return k - multiples.Count;
}
// Function to count the total values
// in the range [L, R]
public static int countValues(int[] arr, int N,
int L, int R)
{
// Count all values in the range
// using exclusion principle
return findNonMultiples(arr, N, R) -
findNonMultiples(arr, N, L - 1);
}
// Driver code
public static void Main(String[] args)
{
int[] arr = { 2, 3, 4, 5, 6 };
int N = arr.Length;
int L = 1;
int R = 20;
// Function Call
Console.WriteLine(countValues(arr, N, L, R));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript program for the above approach
// Function to find the non-multiples
// till k
function findNonMultiples(arr, n, k)
{
// Stores all unique multiples
let multiples = new Set();
// Iterate the array
for (let i = 0; i < n; ++i) {
// For finding duplicates
// only once
if (!multiples.has(arr[i])) {
// Inserting all multiples
// into the set
for (let j = 1;
j <= k / arr[i]; j++) {
multiples.add(arr[i] * j);
}
}
}
// Returning only the count of
// numbers that are not divisible
// by any of the array elements
return k - multiples.size;
}
// Function to count the total values
// in the range [L, R]
function countValues(arr, N, L, R)
{
// Count all values in the range
// using exclusion principle
return findNonMultiples(arr, N, R)
- findNonMultiples(arr, N, L - 1);
}
// Driver Code
let arr = [ 2, 3, 4, 5, 6 ];
let N = arr.length;
let L = 1, R = 20;
// Function Call
document.write(countValues(arr, N, L, R));
// This code is contributed by _saurabh_jaiswal
</script>
Producción:
6
Complejidad de tiempo: O(N*log(log N))
Espacio auxiliar: O(N)