Dada una array de enteros positivos y muchas consultas de divisibilidad. En cada consulta, se nos da un número entero k (> 0), necesitamos contar todos los elementos en la array que son perfectamente divisibles por ‘k’.
Ejemplo:
Input:
2 4 9 15 21 20
k = 2
k = 3
k = 5
Output:
3
3
2
Explanation:
Multiples of '2' in array are:- {2, 4, 20}
Multiples of '3' in array are:- {9, 15, 21}
Multiples of '5' in array are:- {15, 20}
El enfoque simple es recorrer cada valor de ‘k’ en toda la array y contar los múltiplos totales al verificar el módulo de cada elemento de la array, es decir, para cada elemento de i (0 < i < n), verifique si arr[i] % k == 0 o no. Si es perfectamente divisible de k, entonces incremente la cuenta. La complejidad temporal de este enfoque es O(n * k) que no es eficiente para un gran número de consultas de k.
El enfoque eficiente es utilizar el concepto de Tamiz de Eratóstenes . Definamos que el valor máximo en array[] es ‘Max’. Dado que los múltiplos de todos los números en array[] siempre serán menores que Max, iteraremos solo hasta ‘Max’.
Ahora, para cada valor (digamos ‘q’) itere q, 2q, 3q, … tk (tk <= MAX) porque todos estos números son múltiplos de ‘ q ‘. Mientras tanto, almacene el recuento de todos estos números para cada valor de q( 1, 2, … MAX) en la array ans[]. Después de eso, podemos responder todas las consultas en tiempo O (1).
Implementación:
C++
// C++ program to calculate all multiples
// of integer 'k' in array[]
#include <bits/stdc++.h>
using namespace std;
// ans is global pointer so that both countSieve()
// and countMultiples() can access it.
int* ans = NULL;
// Function to pre-calculate all multiples of
// array elements
void countSieve(int arr[], int n)
{
int MAX = *max_element(arr, arr + n);
int cnt[MAX + 1];
// ans is global pointer so that query function
// can access it.
ans = new int[MAX + 1];
// Initialize both arrays as 0.
memset(cnt, 0, sizeof(cnt));
memset(ans, 0, (MAX + 1) * sizeof(int));
// Store the arr[] elements as index
// in cnt[] array
for (int i = 0; i < n; ++i)
++cnt[arr[i]];
// Iterate over all multiples as 'i'
// and keep the count of array[] ( In
// cnt[] array) elements in ans[] array
for (int i = 1; i <= MAX; ++i)
for (int j = i; j <= MAX; j += i)
ans[i] += cnt[j];
return;
}
int countMultiples(int k)
{
// return pre-calculated result
return ans[k];
}
// Driver code
int main()
{
int arr[] = { 2, 4, 9, 15, 21, 20 };
int n = sizeof(arr) / sizeof(arr[0]);
// pre-calculate all multiples
countSieve(arr, n);
int k = 2;
cout << countMultiples(k) << "\n";
k = 3;
cout << countMultiples(k) << "\n";
k = 5;
cout << countMultiples(k) << "\n";
return 0;
}
Java
// Java program to calculate all multiples
// of integer 'k' in array[]
class CountMultiples {
// ans is global array so that both
// countSieve() and countMultiples()
// can access it.
static int ans[];
// Function to pre-calculate all
// multiples of array elements
static void countSieve(int arr[], int n)
{
int MAX = arr[0];
for (int i = 1; i < n; i++)
MAX = Math.max(arr[i], MAX);
int cnt[] = new int[MAX + 1];
// ans is global array so that
// query function can access it.
ans = new int[MAX + 1];
// Store the arr[] elements as
// index in cnt[] array
for (int i = 0; i < n; ++i)
++cnt[arr[i]];
// Iterate over all multiples as 'i'
// and keep the count of array[]
// (In cnt[] array) elements in ans[]
// array
for (int i = 1; i <= MAX; ++i)
for (int j = i; j <= MAX; j += i)
ans[i] += cnt[j];
return;
}
static int countMultiples(int k)
{
// return pre-calculated result
return ans[k];
}
// Driver code
public static void main(String args[])
{
int arr[] = { 2, 4, 9, 15, 21, 20 };
int n = 6;
// pre-calculate all multiples
countSieve(arr, n);
int k = 2;
System.out.println(countMultiples(k));
k = 3;
System.out.println(countMultiples(k));
k = 5;
System.out.println(countMultiples(k));
}
}
/*This code is contributed by Danish Kaleem */
Python3
# Python3 program to calculate all multiples # of integer 'k' in array[] # ans is global array so that both countSieve() # and countMultiples() can access it. ans = [] # Function to pre-calculate all multiples # of array elements # Here, the arguments are as follows # a: given array # n: length of given array def countSieve(arr, n): MAX=max(arr) # Accessing the global array in the function global ans # Initializing "ans" array with zeros ans = [0]*(MAX + 1) # Initializing "cnt" array with zeros cnt = [0]*(MAX + 1) #Store the arr[] elements as index in cnt[] array for i in range(n): cnt[arr[i]] += 1 # Iterate over all multiples as 'i' # and keep the count of array[] ( In # cnt[] array) elements in ans[] array for i in range(1, MAX+1): for j in range(i, MAX+1, i): ans[i] += cnt[j] def countMultiples(k): # Return pre-calculated result return(ans[k]) # Driver code if __name__ == "__main__": arr = [2, 4, 9 ,15, 21, 20] n=len(arr) # Pre-calculate all multiples countSieve(arr, n) k=2 print(countMultiples(2)) k=3 print(countMultiples(3)) k=5 print(countMultiples(5)) # This code is contributed by Pratik Somwanshi
C#
// C# program to calculate all multiples
// of integer 'k' in array[]
using System;
class GFG {
// ans is global array so that both
// countSieve() and countMultiples()
// can access it.
static int[] ans;
// Function to pre-calculate all
// multiples of array elements
static void countSieve(int[] arr, int n)
{
int MAX = arr[0];
for (int i = 1; i < n; i++)
MAX = Math.Max(arr[i], MAX);
int[] cnt = new int[MAX + 1];
// ans is global array so that
// query function can access it.
ans = new int[MAX + 1];
// Store the arr[] elements as
// index in cnt[] array
for (int i = 0; i < n; ++i)
++cnt[arr[i]];
// Iterate over all multiples as
// 'i' and keep the count of
// array[] (In cnt[] array)
// elements in ans[] array
for (int i = 1; i <= MAX; ++i)
for (int j = i; j <= MAX; j += i)
ans[i] += cnt[j];
return;
}
static int countMultiples(int k)
{
// return pre-calculated result
return ans[k];
}
// Driver code
public static void Main()
{
int[] arr = { 2, 4, 9, 15, 21, 20 };
int n = 6;
// pre-calculate all multiples
countSieve(arr, n);
int k = 2;
Console.WriteLine(countMultiples(k));
k = 3;
Console.WriteLine(countMultiples(k));
k = 5;
Console.WriteLine(countMultiples(k));
}
}
// This code is contributed by nitin mittal
PHP
<?php
// PHP program to calculate
// all multiples of integer
// 'k' in array[]
// ans is global array so
// that both countSieve()
// and countMultiples()
// can access it.
$ans;
// Function to pre-calculate all
// multiples of array elements
function countSieve($arr, $n)
{
global $ans;
$MAX = $arr[0];
for ($i = 1; $i < $n; $i++)
$MAX = max($arr[$i], $MAX);
$cnt = array_fill(0, $MAX + 1, 0);
// ans is global array so that
// query function can access it.
$ans = array_fill(0, $MAX + 1, 0);
// Store the arr[] elements
// as index in cnt[] array
for ($i = 0; $i < $n; ++$i)
++$cnt[$arr[$i]];
// Iterate over all multiples as 'i'
// and keep the count of array[]
// (In cnt[] array) elements in ans[]
// array
for ($i = 1; $i <= $MAX; ++$i)
for ($j = $i; $j <= $MAX; $j += $i)
$ans[$i] += $cnt[$j];
return;
}
function countMultiples($k)
{
global $ans;
// return pre-calculated result
return $ans[$k];
}
// Driver code
$arr = array( 2, 4, 9, 15, 21, 20);
$n = 6;
// pre-calculate
// all multiples
countSieve($arr, $n);
$k = 2;
echo countMultiples($k) . "\n";
$k = 3;
echo countMultiples($k) . "\n";
$k = 5;
echo countMultiples($k) . "\n";
// This code is contributed by mits
?>
Javascript
<script>
// Javascript program to calculate all multiples
// of integer 'k' in array[]
// ans is global array so that both
// countSieve() and countMultiples()
// can access it.
let ans = [];
// Function to pre-calculate all
// multiples of array elements
function countSieve(arr, n)
{
let MAX = arr[0];
for (let i = 1; i < n; i++)
MAX = Math.max(arr[i], MAX);
let cnt = Array.from({length: MAX + 1}, (_, i) => 0);
// ans is global array so that
// query function can access it.
ans = Array.from({length: MAX + 1}, (_, i) => 0);
// Store the arr[] elements as
// index in cnt[] array
for (let i = 0; i < n; ++i)
++cnt[arr[i]];
// Iterate over all multiples as 'i'
// and keep the count of array[]
// (In cnt[] array) elements in ans[]
// array
for (let i = 1; i <= MAX; ++i)
for (let j = i; j <= MAX; j += i)
ans[i] += cnt[j];
return;
}
function countMultiples(k)
{
// return pre-calculated result
return ans[k];
}
// driver function
let arr = [ 2, 4, 9, 15, 21, 20 ];
let n = 6;
// pre-calculate all multiples
countSieve(arr, n);
let k = 2;
document.write(countMultiples(k) + "<br/>");
k = 3;
document.write(countMultiples(k) + "<br/>");
k = 5;
document.write(countMultiples(k) + "<br/>");
</script>
Producción
3 3 2
Complejidad de tiempo: O(M*log(M)) donde M es el valor máximo en los elementos de la array.
Espacio auxiliar: O(MAX)
Este artículo es una contribución de Shubham Bansal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a contribuir@geeksforgeeksorg. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA