Question

Write a program to find the number of multiples of x in the array arr that falls between the ith index and the edn of the array

Answer 1

// C++ program to calculate all multiples  

// of integer 'k' in array[]  

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;  

}