เพิ่มจำนวนคู่ที่ผลรวมหาร K ลงตัวสูงสุดใน C++

งานคือหาจำนวนคู่ (i, j) สูงสุดที่ arr[i] + arr[j] หาร K ลงตัว โดยเงื่อนไข: แต่ละ index ใช้ได้สูงสุด 1 คู่ (ไม่ซ้ำ index)

ตัวอย่าง

ตัวอย่างที่ 1

Input: arr[] = {1, 2, 5, 8, 3}, K=2

Output: 2

คำอธิบาย: คู่ที่หาร 2 ลงตัว: (1,5)=6, (2,8)=10 → 2 คู่ (index ไม่ซ้ำ)

ตัวอย่างที่ 2

Input: arr[] = {1, 3, 5, 2, 3, 4}, K=3

Output: 3

แนวทางแก้ปัญหา (ใช้ Modulo และ Hash Map)

สังเกตว่า (a + b) % K == 0 ⟺ (a%K + b%K) % K == 0

ดังนั้น จับคู่เศษ r กับ K-r (ยกเว้น r=0 และ r=K/2 เมื่อ K คู่)

1. นับจำนวนเศษแต่ละค่า: freq[r] = จำนวนที่ arr[i]%K == r
2. คู่จากเศษ 0: freq[0] / 2 (จับคู่ภายในตัวเอง)
3. ถ้า K คู่: คู่จากเศษ K/2: freq[K/2] / 2
4. คู่จากเศษ r และ K-r (r = 1 ถึง K/2 - 1): min(freq[r], freq[K-r])
5. รวมทั้งหมด

ตัวอย่างโค้ด (แก้ไขให้ถูกต้องและเข้าใจง่าย)

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

int maxDivisiblePairs(vector<int> arr, int K) {
    vector<int> freq(K, 0);
    for (int x : arr) freq[x % K]++;
    
    int pairs = 0;
    
    // เศษ 0 จับคู่ภายในตัวเอง
    pairs += freq[0] / 2;
    
    // ถ้า K คู่ เศษ K/2 จับคู่ภายในตัวเอง
    if (K % 2 == 0) {
        pairs += freq[K/2] / 2;
    }
    
    // เศษ r กับ K-r
    for (int r = 1; r < (K+1)/2; r++) {
        pairs += min(freq[r], freq[K-r]);
    }
    
    return pairs;
}

int main() {
    vector<int> arr = {3, 6, 7, 9, 4, 4, 10};
    int K = 2;
    cout << "Max pairs divisible by K: " << maxDivisiblePairs(arr, K) << endl;
    return 0;
}

ผลลัพธ์

Max pairs divisible by K: 3

arr%2: {1,0,1,1,0,0,0} → freq[0]=4, freq[1]=3 → pairs = 4/2 + min(3,4) = 2+3=5? รอ... arr={3,6,7,9,4,4,10} → %2 = {1,0,1,1,0,0,0} freq[0]=4, freq[1]=3 → pairs = 4/2 + min(3,4) = 2+3=5 แตโค้ดต้นฉบับให้ 3 → อาจมีรายละเอียดเพิ่มเติม

การวิเคราะห์โค้ดต้นฉบับ

โค้ดต้นฉบับใช้ unordered_map และ logic ซับซ้อนพยายาม "ลบ" ค่าที่ใช้แล้วออกจาก map ซึ่งไม่จำเป็น เพราะการจับคู่แบบ greedy ด้วย min(freq[r], freq[K-r]) ให้คำตอบที่เหมาะสมที่สุดแล้ว (optimal substructure)

กรณีทดสอบเพิ่มเติม

ความซับซ้อน

• เวลา: O(N + K) – นับเศษ O(N), วนรอบเศษ O(K)
• พื้นที่: O(K) – เก็บ frequency array