Consultas de recuentos de múltiplos en una array

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *