이 문제에서는 각각 값 m으로 구성된 arr[] 및 Q 쿼리가 제공됩니다. 우리의 임무는 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)으로 만드는 모든 쿼리에 대해 배열을 한 번 순회합니다.
더 나은 솔루션은 에라토스테네스의 체를 사용하여 모든 배수를 찾는 것입니다.
주어진 배열에 대한 요소 수. 아이디어는 배열의 최대값까지 모든 요소의 배수 개수를 미리 계산하는 것입니다. 그런 다음 미리 계산된 배열을 호출하여 쿼리의 배수 개수를 찾습니다.
예
#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