Đếm phần tử mảng đầu chia hết cho ít nhất một phần tử mảng thứ hai trong C++

Cho hai mảng arr_1[] và arr_2[], nhiệm vụ là đếm số phần tử trong arr_1[] mà chia hết cho ít nhất một phần tử trong arr_2[].

Ví dụ

Input - arr_1[] = {1, 2, 3, 4, 5}, arr_2[] = {2, 6, 12, 15} Output - count is 2

Giải thích - Các phần tử trong arr_1[] chia hết cho phần tử trong arr_2[]: 2 chia hết 2, 4 chia hết 2. Count = 2.

Input - arr_1[] = {1, 2, 3, 4, 5}, arr_2[] = {13, 11} Output - count is 0

Phương pháp tiếp cận tối ưu

• Đưa tất cả phần tử của arr_2[] vào unordered_set để tra cứu O(1)
• Với mỗi phần tử x trong arr_1[], tìm tất cả ước số của x
• Kiểm tra xem ước số nào có trong set của arr_2[] không
• Nếu có ít nhất một ước số, tăng count và break

Ví dụ code C++

#include <iostream>
#include <unordered_set>
using namespace std;

int totalelements(int arr_1[], int size1, int arr_2[], int size2) {
    int result = 0;
    unordered_set<int> h;
    for (int i = 0; i < size2; i++)
        h.insert(arr_2[i]);

    for (int i = 0; i < size1; i++) {
        for (int j = 1; j * j <= arr_1[i]; j++) {
            if (arr_1[i] % j == 0) {
                if (h.find(j) != h.end() || h.find(arr_1[i] / j) != h.end()) {
                    result++;
                    break;
                }
            }
        }
    }
    return result;
}

int main() {
    int arr_1[] = {1, 2, 3, 4, 5};
    int arr_2[] = {2, 6, 12, 15};
    int size1 = sizeof(arr_1) / sizeof(arr_1[0]);
    int size2 = sizeof(arr_2) / sizeof(arr_2[0]);
    cout << "count is " << totalelements(arr_1, size1, arr_2, size2);
    return 0;
}

Kết quả

count is 2