ขยายขนาดอาร์เรย์สูงสุดโดยลบ K ซับอาร์เรย์ให้เหลือเฉพาะจำนวนเฉพาะใน C++

ภาพรวมปัญหา

ลบ K ซับอาร์เรย์พอดีจากอาร์เรย์ Arr[] ขนาด N ให้อิลิเมนต์ที่เหลือเป็นจำนวนเฉพาะทั้งหมด และขนาดอาร์เรย์ที่เหลือต้องมากที่สุด

ตัวอย่าง

Input: Arr[] = {4, 3, 3, 4, 3, 4, 3}, K = 2
Output: 3
Explanation: ลบ Arr[0] และ Arr[3..5] เหลือ {3,3,3}

Input: Arr[] = {7, 6, 2, 11, 8, 3, 12}, K = 2
Output: 3
Explanation: ลบ Arr[1] และ Arr[4..6] เหลือ {7,2,11}

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

• ใช้ Sieve of Eratosthenes หาจำนวนเฉพาะ
• เก็บดัชนีของจำนวนประกอบ (composite)
• คำนวณจำนวนจำนวนเฉพาะระหว่างจำนวนประกอบติดกัน
• จัดกลยุทธ์การลบตาม K เทียบกับจำนวนจำนวนประกอบ

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

#include <bits/stdc++.h>
using namespace std;

const int Num = 1e5;
bool prime[Num];

void sieve() {
    for (int i = 2; i < Num; i++) {
        if (!prime[i]) {
            for (int j = i + i; j < Num; j += i)
                prime[j] = 1;
        }
    }
    prime[1] = 1;
}

int MaxSize(int* arr, int N, int K) {
    vector vect, diff;
    for (int i = 0; i < N; i++)
        if (prime[arr[i]]) vect.push_back(i);
    
    for (int i = 1; i < vect.size(); i++)
        diff.push_back(vect[i] - vect[i-1] - 1);
    
    sort(diff.begin(), diff.end());
    for (int i = 1; i < diff.size(); i++)
        diff[i] += diff[i-1];
    
    if (K > N || (K == 0 && vect.size())) return -1;
    else if (vect.size() <= K) return (N - K);
    else {
        int tt = vect.size() - K;
        int sum = diff[tt - 1];
        return N - (vect.size() + sum);
    }
}

int main() {
    sieve();
    int arr[] = { 7, 2, 3, 4, 3, 6, 3, 3 };
    int N = sizeof(arr) / sizeof(arr[0]);
    int K = 2;
    cout << MaxSize(arr, N, K);
    return 0;
}

ผลลัพธ์

6