এই সমস্যাতে, আমাদের একটি অ্যারে arr[] এবং Q সংখ্যক কোয়েরি দেওয়া আছে, প্রতিটি একটি মান m দিয়ে গঠিত। আমাদের কাজ হলো C++-এ অ্যারে-এ মাল্টিপল কাউন্ট করার কোয়েরি সমাধান করার প্রোগ্রাম লিখা।
সমস্যা বর্ণনা
কোয়েরি সমাধানের জন্য, m-এর সব মাল্টিপেল সংখ্যা কাউন্ট করতে হবে। এর জন্য আমরা m দিয়ে বিভাজ্য এলিমেন্টগুলো চেক করব।
উদাহরণ দিয়ে বুঝি,
ইনপুট:arr[] = {4, 7, 3, 8, 12, 15}
Q = 3 query[] = {2, 3, 5}
আউটপুট:3 3 1
ব্যাখ্যা
কোয়েরি ১: m = 2, অ্যারেতে মাল্টিপেল = 4, 8, 12। কাউন্ট = ৩।
কোয়েরি ২: m = 3, অ্যারেতে মাল্টিপেল = 3, 12, 15। কাউন্ট = ৩।
কোয়েরি ৩: m = 5, অ্যারেতে মাল্টিপেল = 15। কাউন্ট = ১।
সমাধান পদ্ধতি
একটি সহজ সমাধান হচ্ছে প্রতিটি কোয়েরি মান জন্য অ্যারে ট্রাভার্স করে 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
