Truy vấn số bội số trong một mảng trong C ++

Trong bài toán này, chúng ta được đưa ra một truy vấn arr [] và Q, mỗi truy vấn bao gồm một giá trị m. Nhiệm vụ của chúng tôi là tạo một chương trình để giải quyết các Truy vấn về số bội số trong một mảng trong C ++.

Mô tả vấn đề

Để giải quyết các truy vấn, chúng ta cần đếm tất cả các số là bội số của m. Đối với điều này, chúng tôi sẽ kiểm tra các phần tử chia hết cho m.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào :arr [] ={4, 7, 3, 8, 12, 15}

Q =3 truy vấn [] ={2, 3, 5}

Bỏ qua :3 3 1

Giải thích

Truy vấn 1:m =2, bội số trong mảng =4, 8, 12. Count =3.

Truy vấn 2:m =3, bội số trong mảng =3, 12, 15. Đếm =3.

Truy vấn 3:m =5, bội số trong mảng =15. Đếm =1.

Phương pháp tiếp cận giải pháp

Một giải pháp đơn giản là duyệt qua mảng cho mỗi giá trị truy vấn và đếm số phần tử của mảng chia hết cho m.

Ví dụ

#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;
}

Đầu ra

The count of multiples in array 3
The count of multiples in array 3
The count of multiples in array 1

Giải pháp này duyệt mảng một lần cho mỗi truy vấn làm cho độ phức tạp về thời gian là O (Q * n).

Một giải pháp tốt hơn là sử dụng Sieve of Eratosthenes để tìm tất cả các bội số

và số phần tử cho mảng đã cho. Ý tưởng là tính toán trước tổng số bội số của tất cả các phần tử cho đến giá trị lớn nhất của mảng. Và sau đó gọi mảng được tính toán trước để tìm số bội số cho các truy vấn.

Ví dụ

#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;
}

Đầu ra

The count of multiples in array 3
The count of multiples in array 3
The count of multiples in array 1