หาจำนวนซับอาร์เรย์ที่มีผลรวมเป็นเลขคู่ด้วย C++

ภาพรวมปัญหา

ได้รับอาร์เรย์ arr[] ขนาด N ต้องหาจำนวนซับอาร์เรย์ (subarray) ที่มีผลรวมเป็นเลขคู่

ตัวอย่าง

อินพุต

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

เอาต์พุต

28

วิธีแก้ปัญหา

วิธีที่ 1: Brute Force - O(n²)

คำนวณผลรวมของทุกซับอาร์เรย์ แล้วนับที่เป็นเลขคู่

โค้ดตัวอย่าง

#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;
}

วิธีที่ 2: Prefix Sum + Counting - O(n) ⭐

ใช้คุณสมบัติ: ผลรวมคู่ = (prefix_sum[j] - prefix_sum[i]) % 2 == 0

นั่นคือ prefix_sum[j] และ prefix_sum[i] ต้องมี parity เหมือนกัน (คู่คู่ หรือ คี่คี่)

นับจำนวน prefix sum ที่เป็นคู่ (count0) และคี่ (count1) แล้วคำนวณ:

จำนวนคู่ = C(count0, 2) + C(count1, 2) = count0*(count0-1)/2 + count1*(count1-1)/2

โค้ดตัวอย่าง (มีในบทความต้นฉบับแต่ปนกับโค้ดอื่น)

#include <iostream>
using namespace std;

int countEvenSumSubArray(int arr[], int n) {
    int temp[2] = {1, 0};  // temp[0] = จำนวน prefix sum คู่ (เริ่มที่ 1 เพราะ sum=0)
    int count = 0, sum = 0;
    
    for (int i = 0; i < n; i++) {
        sum = ((sum + arr[i]) % 2 + 2) % 2;  // prefix sum mod 2
        temp[sum]++;
    }
    
    count += (temp[0] * (temp[0] - 1) / 2);
    count += (temp[1] * (temp[1] - 1) / 2);
    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;
}

เอาต์พุต

The count of Subarrays with even sum is 4

สรุป

วิธี Prefix Sum + Counting เร็วกว่ามาก O(n) เทียบกับ O(n²) เหมาะสำหรับ N ใหญ่