Đếm cặp có thứ tự với tổng chẵn/lẻ trong mảng C++

Cho mảng n số nguyên dương. Đếm số cặp có thứ tự (arr[x], arr[y]) với x ≠ y sao cho tổng là chẵn hoặc lẻ. Cặp (a,b) và (b,a) tính riêng biệt.

Ví dụ minh họa

Ví dụ 1:

• Input: Arr = {1, 1, 2, 3}, N = 4
• Output: Even Sum pairs: 6, Odd Sum pairs: 6

Ví dụ 2:

• Input: Arr = {2, 2, 2}, N = 3
• Output: Even Sum pairs: 6, Odd Sum pairs: 0

Phân tích toán học

• Tổng chẵn: (chẵn + chẵn) hoặc (lẻ + lẻ)
• Tổng lẻ: (chẵn + lẻ) hoặc (lẻ + chẵn)

Gọi: even = số phần tử chẵn, odd = số phần tử lẻ.

Với cặp có thứ tự (x ≠ y):

• Even pairs = even×(even-1) + odd×(odd-1)
• Odd pairs = 2 × even × odd

Mã nguồn C++ (Vét cạn O(n²))

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

void countPairs(int arr[], int n) {
    int evenSum = 0, oddSum = 0;
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            int sum = arr[i] + arr[j];
            if (sum % 2 == 0) evenSum += 2;  // (i,j) và (j,i)
            else oddSum += 2;
        }
    }
    cout << "Even Sum pairs: " << evenSum;
    cout << endl << "Odd Sum pairs: " << oddSum;
}

int main() {
    int arr[] = {1, 2, 3, 2};
    int n = sizeof(arr) / sizeof(int);
    countPairs(arr, n);
    return 0;
}

Kết quả chạy chương trình

Even Sum pairs: 4
Odd Sum pairs: 8

Tối ưu hóa O(n) - Công thức toán học

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

void countPairsOptimized(int arr[], int n) {
    long long even = 0, odd = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] % 2 == 0) even++;
        else odd++;
    }
    long long evenPairs = even * (even - 1) + odd * (odd - 1);
    long long oddPairs = 2 * even * odd;
    
    cout << "Even Sum pairs: " << evenPairs << endl;
    cout << "Odd Sum pairs: " << oddPairs;
}

Độ phức tạp