นับจำนวนองค์ประกอบที่หารด้วยอย่างน้อยหนึ่งตัวในอีกอาร์เรย์หนึ่งใน C++

เราได้รับอาร์เรย์สองชุด arr_1[] และ arr_2[] งานคือการนับจำนวนองค์ประกอบใน arr_1 ที่หารด้วยอย่างน้อยหนึ่งองค์ประกอบใน arr_2 ลงตัว

ตัวอย่าง

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

คำอธิบาย − ใน arr_1 มี 5 องค์ประกอบ arr_2 มี 4 องค์ประกอบ องค์ประกอบใน arr_1 ที่หารด้วยสมาชิกใน arr_2 ลงตัวมี 2 ตัว

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

คำอธิบาย − ไม่มีองค์ประกอบใน arr_1 ที่หารด้วยสมาชิกใน arr_2 ลงตัว

แนวทางการแก้ปัญหา

• สร้างอาร์เรย์สองชุด
• คำนวณขนาดทั้งสองอาร์เรย์
• ใช้ unordered_set เก็บค่าของ arr_2 เพื่อค้นหาเร็ว
• วนลูปแต่ละค่าใน arr_1 หาตัวหารทั้งหมด (ตรวจสอบจนถึงรากที่สอง)
• ถ้าพบตัวหารอยู่ใน set ของ arr_2 ให้เพิ่มตัวนับและ break

ตัวอย่างโค้ด C++

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

int totalElements(int arr1[], int size1, int arr2[], int size2) {
    int result = 0;
    unordered_set h;
    for (int i = 0; i < size2; i++) h.insert(arr2[i]);
    
    for (int i = 0; i < size1; i++) {
        for (int j = 1; j * j <= arr1[i]; j++) {
            if (arr1[i] % j == 0) {
                if (h.count(j) || h.count(arr1[i] / j)) {
                    result++;
                    break;
                }
            }
        }
    }
    return result;
}

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

ผลลัพธ์

count is 2