Đếm cặp trong mảng có tổng chia hết cho 4 trong C++

Giới thiệu

Trường hợp đặc biệt của bài toán chia hết cho k với k = 4. Cho mảng, đếm cặp (i, j) có tổng chia hết cho 4.

Ví dụ

• arr = [4,1,2,0,2] → 2 cặp: (4,0), (2,2)
• arr = [2,4,8,6,10] → 4 cặp: (2,6), (2,10), (4,8), (6,10)

Ý tưởng giải thuật (Tối ưu cho k=4)

Chỉ có 4 phần dư: 0, 1, 2, 3. Cặp hợp lệ:

• (0,0): freq[0]*(freq[0]-1)/2
• (2,2): freq[2]*(freq[2]-1)/2
• (1,3): freq[1]*freq[3]

Ví dụ triển khai (C++)

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

int countPairsDivisibleBy4(vector<int> arr) {
    vector<int> freq(4, 0);
    for (int x : arr)
        freq[x % 4]++;
    
    int count = 0;
    count += freq[0] * (freq[0] - 1) / 2; // (0,0)
    count += freq[2] * (freq[2] - 1) / 2; // (2,2)
    count += freq[1] * freq[3];           // (1,3)
    return count;
}

int main() {
    vector<int> arr = {4, 1, 2, 0, 2};
    cout << "So cap tong chia het cho 4: " << countPairsDivisibleBy4(arr); // 2
    return 0;
}

Đầu vào

[4,1,2,0,2]

Đầu ra

2