इस समस्या में, हमें एक एआर [] और क्यू प्रश्न दिए गए हैं, जिनमें से प्रत्येक का मान m है। हमारा कार्य C++ में एक सरणी में गुणकों की संख्या के लिए प्रश्नों को हल करने के लिए एक प्रोग्राम बनाना है।
समस्या का विवरण
प्रश्नों को हल करने के लिए, हमें उन सभी संख्याओं को गिनना होगा जो m के गुणज हों। इसके लिए हम m से विभाज्य तत्वों की जाँच करेंगे।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट :arr[] ={4, 7, 3, 8, 12, 15}
क्यू =3 क्वेरी [] ={2, 3, 5}
आउटपुट :3 3 1
स्पष्टीकरण
प्रश्न 1:m =2, सरणी में गुणज =4, 8, 12. गणना =3.
प्रश्न 2:m =3, सरणी में गुणज =3, 12, 15. गणना =3.
प्रश्न 3:m =5, सरणी में गुणज =15. गणना =1.
समाधान दृष्टिकोण
एक सरल उपाय यह है कि प्रत्येक क्वेरी मान के लिए सरणी को ट्रेस किया जाए और m से विभाज्य सरणी के तत्वों की संख्या की गणना की जाए।
उदाहरण
#include <iostream>
using namespace std;
int solveQuery(int arr[], int N, int m){
int count = 0;
for(int i = 0; i < N; i++){
if(arr[i]%m == 0)
count++;
}
return count;
}
int main(){
int arr[] = {4, 7, 3, 8, 12, 15};
int N = sizeof(arr)/sizeof(arr[0]);
int Q = 3;
int query[] = {2, 3, 5};
for(int i = 0; i < Q; i++)
cout<<"The count of multiples in array "<<solveQuery(arr, N,query[i])<<endl;
return 0;
} आउटपुट
The count of multiples in array 3 The count of multiples in array 3 The count of multiples in array 1
यह समाधान, समय जटिलता O(Q*n) बनाने वाली प्रत्येक क्वेरी के लिए एक बार सरणी को ट्रैवर्स करता है।
सभी गुणकों को खोजने के लिए एराटोस्थनीज की छलनी का उपयोग करके एक बेहतर समाधान है
और दिए गए सरणी के लिए तत्व मायने रखता है। विचार सरणी के अधिकतम मूल्य तक सभी तत्वों के गुणकों की गणना पूर्व-गणना करना है। और फिर प्रश्नों के लिए गुणकों की संख्या ज्ञात करने के लिए पूर्व-परिकलित सरणी को कॉल करना।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int preCalcCount[10001];
void PreCalculateMultiples(int arr[], int N){
int maxVal = *max_element(arr, arr + N);
int count[maxVal + 1];
memset(count, 0, sizeof(count));
memset(preCalcCount, 0, (maxVal + 1) * sizeof(int));
for (int i = 0; i < N; ++i)
++count[arr[i]];
for (int i = 1; i <= maxVal; ++i)
for (int j = i; j <= maxVal; j += i)
preCalcCount[i] += count[j];
}
int main(){
int arr[] = {4, 7, 3, 8, 12, 15};
int N = sizeof(arr)/sizeof(arr[0]);
int Q = 3;
int query[Q] = {2, 3, 5};
PreCalculateMultiples(arr, N);
for(int i = 0; i < Q; i++)
cout<<"The count of multiples in array"<<preCalcCount[query[i]]<<endl;
return 0;
} आउटपुट
The count of multiples in array 3 The count of multiples in array 3 The count of multiples in array 1