จำนวนสมาชิกน้อยที่สุดที่ควรลบเพื่อทำให้อาร์เรย์ดี (Good) ด้วย C++

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

กำหนดอาร์เรย์ "arr" งานคือหาจำนวนสมาชิกน้อยที่สุดที่ต้องลบเพื่อทำให้อาร์เรย์เป็นอาร์เรย์ที่ดี (Good Array)

ลำดับ a1, a2, a3 ... an เรียกว่าดี (Good) หากสำหรับแต่ละสมาชิก a[i] มีสมาชิก a[j] (i ไม่เท่ากับ j) อยู่ที่ทำให้ a[i] + a[j] เป็นกำลังของสอง (Power of Two)

arr1[] = {1, 1, 7, 1, 5}

ในอาร์เรย์ข้างต้น ถ้าเราลบสมาชิก '5' อาร์เรย์จะกลายเป็นอาร์เรย์ที่ดี หลังจากนี้ คู่ใดๆ ของ arr[i] + arr[j] จะเป็นกำลังของสอง -

• arr[0] + arr[1] = (1 + 1) = 2 ซึ่งเป็นกำลังของสอง
• arr[0] + arr[2] = (1 + 7) = 8 ซึ่งเป็นกำลังของสอง

อัลกอริทึม

1. เราต้องลบเฉพาะ a[i] ที่ไม่มี a[j] ใดๆ ที่ทำให้ a[i] + a[j] เป็นกำลังของ 2
2. สำหรับแต่ละค่า หาจำนวนครั้งที่ปรากฏในอาร์เรย์
3. ตรวจสอบว่า a[i] ไม่มีคู่ a[j]

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

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

int minDeleteRequred(int *arr, int n) {
    map<int, int> frequency;
    for (int i = 0; i < n; ++i) {
        frequency[arr[i]]++;
    }
    int delCnt = 0;
    for (int i = 0; i < n; ++i) {
        bool doNotRemove = false;
        for (int j = 0; j < 31; ++j) {
            int pair = (1 << j) - arr[i];
            if (frequency.count(pair) &&
                (frequency[pair] > 1 ||
                (frequency[pair] == 1 && pair != arr[i]))) {
                doNotRemove = true;
                break;
            }
        }
        if (!doNotRemove) {
            ++delCnt;
        }
    }
    return delCnt;
}

int main() {
    int arr[] = {1, 1, 7, 1, 5};
    cout << "Minimum elements to be deleted = " << minDeleteRequred(arr, SIZE(arr)) << endl;
    return 0;
}

ผลลัพธ์

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

Minimum elements to be deleted = 1