Đếm cặp từ hai mảng có tổng chẵn trong C++

Giới thiệu

Cho hai mảng arr1, arr2. Đếm số cặp (x từ arr1, y từ arr2) sao cho x + y là số chẵn.

Quan sát quan trọng

Tổng chẵn ⇔ cả hai cùng chẵn hoặc cả hai cùng lẻ.

Số cặp = (số chẵn arr1 × số chẵn arr2) + (số lẻ arr1 × số lẻ arr2). Độ phức tạp O(n+m).

Ví dụ

arr1 = [2,3,7,1,4] (chẵn: 2,4; lẻ: 3,7,1), arr2 = [2,4,1,3] (chẵn: 2,4; lẻ: 1,3)

Kết quả = 2×2 + 3×2 = 4 + 6 = 10

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

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

long long countEvenSumPairs(vector<int> a, vector<int> b) {
    long long evenA = 0, oddA = 0, evenB = 0, oddB = 0;
    for (int x : a) (x % 2 == 0 ? evenA : oddA)++;
    for (int x : b) (x % 2 == 0 ? evenB : oddB)++;
    return evenA * evenB + oddA * oddB;
}

int main() {
    vector<int> a = {2, 3, 7, 1, 4};
    vector<int> b = {2, 4, 1, 3};
    cout << "So cap tong chan: " << countEvenSumPairs(a, b); // 10
    return 0;
}

Đầu vào