Tối đa hóa số cặp tổng chia hết cho K trong C++

Cho mảng arr[] chứa N số nguyên. Nhiệm vụ: tìm số cặp (i,j) tối đa sao cho arr[i] + arr[j] chia hết cho K. Mỗi chỉ số chỉ được dùng trong tối đa 1 cặp.

Ví dụ 1

Input

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

Output – 2

Giải thích: Các cặp: (1,5)=6, (2,8)=10. Cả 2 đều chia hết cho 2. Các cặp khác có thể: (1,3), (2,8) hoặc (5,3), (2,8) nhưng số cặp max vẫn là 2.

Ví dụ 2

Input

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

Output – 3

Thuật toán (dùng modulo và hash map)

1. Tính余 số (remainder) của mỗi phần tử modulo K: r = arr[i] % K.
2. Đếm tần suất mỗi remainder trong unordered_map.
3. Cặp (a,b) chia hết cho K ⟺ (a%K + b%K) % K == 0.
   • Remainder 0: cặp với nhau → số cặp = freq[0] / 2.
   • Remainder K/2 (nếu K chẵn): cặp với nhau → freq[K/2] / 2.
   • Remainder r và K-r (r ≠ 0, r ≠ K/2): cặp chéo → min(freq[r], freq[K-r]).
4. Tổng số cặp là tổng các trường hợp trên.

Ví dụ code

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

int maxPairsDivisibleByK(int arr[], int size, int K) {
    unordered_map<int, int> freq;
    for (int i = 0; i < size; i++) {
        freq[arr[i] % K]++;
    }
    
    int count = 0;
    
    // Xử lý remainder 0
    count += freq[0] / 2;
    freq[0] %= 2;
    
    // Xử lý remainder K/2 nếu K chẵn
    if (K % 2 == 0) {
        count += freq[K/2] / 2;
        freq[K/2] %= 2;
    }
    
    // Xử lý các cặp (r, K-r)
    for (int r = 1; r < (K + 1) / 2; r++) {
        int complement = K - r;
        int pairs = min(freq[r], freq[complement]);
        count += pairs;
        freq[r] -= pairs;
        freq[complement] -= pairs;
    }
    
    return count;
}

int main() {
    int arr[] = {3, 6, 7, 9, 4, 4, 10};
    int size = sizeof(arr) / sizeof(arr[0]);
    int K = 2;
    cout << "Max pairs divisible by K: " << maxPairsDivisibleByK(arr, size, K) << endl;
    return 0;
}

Kết quả

Max pairs divisible by K: 3

Giải thích: arr%2 = {1,0,1,1,0,0,0}. freq[0]=4, freq[1]=3. - Remainder 0: 4/2 = 2 cặp. - Remainder 1: cặp với nhau (vì K=2, 1+1=2≡0): 3/2 = 1 cặp. - Tổng: 3 cặp.

Độ phức tạp: O(N) thời gian, O(K) không gian.