C++の配列内の倍数のカウントのクエリ

この問題では、それぞれ値mで構成されるarr[]クエリとQクエリが与えられます。私たちのタスクは、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<<"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）にするクエリごとに1回配列をトラバースします。

より良い解決策は、エラトステネスのふるいを使用してすべての倍数を見つけることです

指定された配列の要素数。アイデアは、配列の最大値までのすべての要素の倍数のカウントを事前に計算することです。次に、事前に計算された配列を呼び出して、クエリの倍数の数を見つけます。

例

#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