สมาชิกอาร์เรย์ที่ไม่หารด้วยสมาชิกอาร์เรย์อื่นได้เลยใน C++

ปัญหา

ได้รับอาร์เรย์ arr1[] และ arr2[] หาสมาชิกใน arr1 ที่ ไม่หารลงตัว ด้วยสมาชิกใดๆ ใน arr2

ตัวอย่าง

arr1 = {17, 15, 5, 12, 8}, arr2 = {5, 4}

Output: 17 (เพราะ 15 หาร 5 ลงตัว, 5 หาร 5 ลงตัว, 12 หาร 4 ลงตัว, 8 หาร 4 ลงตัว)

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

วิธีที่ 1: Naive O(N×M) วนลูปสองชั้น ตรวจสอบทุกคู่

วิธีที่ 2: Efficient O(N + M + Max) สร้างอาร์เรย์ mark[] ขนาด max(arr1) ทำเครื่องหมายทุกจำนวนที่หารด้วยสมาชิก arr2 ได้ แล้วตรวจสอบ arr1

โปรแกรมตัวอย่าง (วิธีที่ 2)

#include <iostream>
using namespace std;

void findEleNotDivisible(int arr1[], int arr2[], int n1, int n2) {
    int maxEle = *max_element(arr1, arr1 + n1);
    vector<bool> marked(maxEle + 1, false);
    
    for (int i = 0; i < n2; i++)
        for (int j = arr2[i]; j <= maxEle; j += arr2[i])
            marked[j] = true;
    
    for (int i = 0; i < n1; i++)
        if (!marked[arr1[i]])
            cout << arr1[i] << " ";
}

int main() {
    int arr1[] = {17, 15, 5, 12, 23, 8};
    int arr2[] = {5, 4};
    findEleNotDivisible(arr1, arr2, 6, 2);
    return 0;
}

ผลลัพธ์

17 23