จำนวนการดำเนินการน้อยที่สุดเพื่อลบสมาชิกทั้งหมดของอาร์เรย์ด้วย C++

ข้อความโจทย์

กำหนดอาร์เรย์จำนวนเต็ม arr งานคือพิมพ์จำนวนการดำเนินการขั้นต่ำที่จำเป็นเพื่อลบสมาชิกทั้งหมดของอาร์เรย์ ขณะลบสมาชิกมีข้อจำกัดดังนี้ -

• สามารถเลือกสมาชิกใดก็ได้จากอาร์เรย์แบบสุ่ม และสมาชิกทุกตัวที่หารด้วยมันลงตัวจะถูกลบออกจากอาร์เรย์

ถ้า arr[] = {2, 4, 15, 10, 8, 5, 3} แล้วต้องการ 3 การดำเนินการเพื่อลบสมาชิกทั้งหมด -

• ถ้าเลือก 2 จะลบ {2, 4, 10, 8}
• ถ้าเลือก 5 จะลบ {5, 15}
• ถ้าเลือก 3 จะลบ {3}

อัลกอริทึม

1. เรียงอาร์เรย์จากน้อยไปมาก และนับจำนวนครั้งที่แต่ละสมาชิกปรากฏ
2. สำหรับแต่ละสมาชิกที่ยังไม่ถูกทำเครื่องหมาย เริ่มจากต้นทาง ทำเครื่องหมายสมาชิกทั้งหมดที่หารด้วยสมาชิกที่เลือกลงตัว และเพิ่มตัวนับผลลัพธ์

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

#include <iostream>
#include <algorithm>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
#define MAX 100
using namespace std;

int getMinOperations(int *arr, int n) {
    int map[MAX] = {0};
    sort(arr, arr + n);
    for (int i = 0; i < n; ++i) {
        map[arr[i]]++;
    }
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        if (map[arr[i]]) {
            for (int j = i; j < n; ++j) {
                if (arr[j] % arr[i] == 0) {
                    map[arr[j]] = 0;
                }
            }
            ++cnt;
        }
    }
    return cnt;
}

int main() {
    int arr[] = {2, 4, 15, 10, 8, 5, 3};
    cout << "Minimum required operations = " << getMinOperations(arr, SIZE(arr)) << endl;
    return 0;
}

ผลลัพธ์

เมื่อคอมไพล์และรันโปรแกรมด้านบน จะได้ผลลัพธ์ดังนี้ -

Minimum required operations = 3