समस्या विवरण
इस समस्या में, हमें एक सरणी arr[] और Q क्वेरीज़ दी गई हैं जिनमें से प्रत्येक में एक मान m होता है। हमारा कार्य C++ में सरणी में गुणकों की संख्या के लिए क्वेरीज़ को हल करने के लिए एक प्रोग्राम बनाना है।
क्वेरीज़ को हल करने के लिए, हमें उन सभी संख्याओं को गिनना होगा जो m के गुणक हैं। इसके लिए हम m से विभाज्य तत्वों की जांच करेंगे।
उदाहरण
इनपुट: arr[] = {4, 7, 3, 8, 12, 15}
Q = 3 query[] = {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 << "सरणी में गुणकों की संख्या " << solveQuery(arr, N, query[i]) << endl;
return 0;
}
आउटपुट
सरणी में गुणकों की संख्या 3 सरणी में गुणकों की संख्या 3 सरणी में गुणकों की संख्या 1
यह समाधान, प्रत्येक क्वेरी के लिए एक बार सरणी को पार करता है जिससे समय जटिलता O(Q*n) होती है।
एक बेहतर समाधान एराटोस्थनीज की छलनी (Sieve of Eratosthenes) का उपयोग करके दिए गए सरणी के लिए सभी गुणकों और तत्वों की संख्या ढूंढना है। विचार सरणी के अधिकतम मान तक सभी तत्वों के गुणकों की संख्या की पूर्व-गणना करना है। और फिर क्वेरीज़ के लिए गुणकों की संख्या ढूंढने के लिए पूर्व-गणना सरणी को कॉल करना।
कार्यक्रम उदाहरण (अनुकूलित दृष्टिकोण)
#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 << "सरणी में गुणकों की संख्या " << preCalcCount[query[i]] << endl;
return 0;
}
आउटपुट
सरणी में गुणकों की संख्या 3 सरणी में गुणकों की संख्या 3 सरणी में गुणकों की संख्या 1
