Đếm cặp có thứ tự với tích 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ích 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 Product pairs: 6, Odd Product pairs: 6

Ví dụ 2:

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

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

• Tích chẵn: ít nhất một trong hai số là chẵn
• Tích lẻ: cả hai số đều lẻ

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 = Tổng cặp - Odd pairs = n×(n-1) - odd×(odd-1)
• Odd pairs = odd × (odd - 1)

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

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

void countPairs(int arr[], int n) {
    int evenProd = 0, oddProd = 0;
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            int prod = arr[i] * arr[j];
            if (prod % 2 == 0) evenProd += 2;
            else oddProd += 2;
        }
    }
    cout << "Even Product pairs: " << evenProd;
    cout << endl << "Odd Product pairs: " << oddProd;
}

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

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

Even Product pairs: 6
Odd Product pairs: 6

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 totalOrdered = 1LL * n * (n - 1);
    long long oddPairs = odd * (odd - 1);
    long long evenPairs = totalOrdered - oddPairs;
    
    cout << "Even Product pairs: " << evenPairs << endl;
    cout << "Odd Product pairs: " << oddPairs;
}

Độ phức tạp