এই সমস্যায়, আমাদের একটি arr[] এবং Q প্রশ্ন দেওয়া হয়েছে যার প্রতিটিতে একটি মান m রয়েছে। আমাদের কাজ হল C++ এ একটি অ্যারেতে গুণিতক সংখ্যার জন্য প্রশ্নের সমাধান করার জন্য একটি প্রোগ্রাম তৈরি করা।
সমস্যা বর্ণনা
প্রশ্নগুলি সমাধান করার জন্য, আমাদের m এর গুণিতক সমস্ত সংখ্যা গণনা করতে হবে। এর জন্য আমরা m দ্বারা বিভাজ্য উপাদানগুলি পরীক্ষা করব।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট :arr[] ={4, 7, 3, 8, 12, 15}
Q =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) করে তোলে।
একটি ভাল সমাধান হল সমস্ত মাল্টিপল খুঁজে বের করার জন্য 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<<"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
