Tìm số mảng con có tổng chẵn trong C++

Giới thiệu

Cho mảng arr[] N phần tử. Đếm số mảng con (subarray) có tổng chẵn.

Ví dụ minh họa

Đầu vào

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

Đầu ra

28

Phương pháp 1: Brute Force - O(n²)

Tính tổng mọi mảng con và đếm những cái tổng chẵn.

Chương trình minh họa

#include <iostream>
using namespace std;

int countEvenSumSubArray(int arr[], int n) {
    int evenSumCount = 0, sum = 0;
    for (int i = 0; i <= n-1; i++) {
        sum = 0;
        for (int j = i; j <= n-1; j++) {
            sum += arr[j];
            if (sum % 2 == 0)
                evenSumCount++;
        }
    }
    return evenSumCount;
}

int main() {
    int arr[] = {2, 1, 4, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The count of Subarrays with even sum is " << countEvenSumSubArray(arr, n);
    return 0;
}

Đầu ra

The count of Subarrays with even sum is 8

Phương pháp 2: Toán học - O(n)

Sử dụng tính chất: tổng chẵn ⇔ số phần tử lẻ trong mảng con là chẵn. Đếm tiền tố có tổng chẵn/lẻ, áp dụng công thức tổ hợp.

Chương trình minh họa

#include <iostream>
using namespace std;

int countEvenSumSubArray(int arr[], int n) {
    int temp[2] = {1, 0}; // temp[0]: số tiền tố tổng chẵn, temp[1]: tổng lẻ
    int count = 0, sum = 0;
    for (int i = 0; i <= n-1; i++) {
        sum = ((sum + arr[i]) % 2 + 2) % 2; // tiền tố mod 2
        temp[sum]++;
    }
    count += (temp[0] * (temp[0] - 1) / 2); // chọn 2 tiền tố tổng chẵn
    count += (temp[1] * (temp[1] - 1) / 2); // chọn 2 tiền tố tổng lẻ
    return count;
}

int main() {
    int arr[] = {2, 1, 4, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The count of Subarrays with even sum is " << countEvenSumSubArray(arr, n);
    return 0;
}

Đầu ra

The count of Subarrays with even sum is 4