program to calculate the multiple of items in a list
Answers
Given an array of positive integers and many queries for divisibility. In every query, we are given an integer k ( > 0), we need to count all elements in the array which are perfectly divisible by ‘k’.
Example:
Input:
2 4 9 15 21 20
k = 2
k = 3
k = 5
Output:
3
3
2
Explanations
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}
Recommended: Please try your approach on {IDE} first, before moving on to the solution.
Simple Approach is to traverse over every value of ‘k’ in whole array and count total multiples by checking modulas of every element of array i.e., for every element of i (0 < i < n), check whether arr[i] % k == 0 or not. If it's perfectly divisible of k, then increment count. Time complexity of this approach is O(n * k) which is not efficient for large number of queries of k.
Efficient approach is to use the concept of Sieve of Eratosthenes. Let’s define the maximum value in array[] is ‘Max’. Since multiples of all numbers in array[] will always be less than Max, therefore we will iterate up-to ‘Max’ only.
Now for every value(say ‘q’) iterate q, 2q, 3q, … t.k(tk <= MAX) because all these numbers are multiples of 'q‘ .Meanwhile store the count of all these number for every value of q(1, 2, … MAX) in ans[] array. After that we can answer every query in O(1) time.
// 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;
}