นับ Subarray ที่มีจำนวนเลขคู่และเลขคี่เท่ากันใน C++

เราได้รับอาร์เรย์จำนวนเต็มบวก เป้าหมายคือหา subarray ที่มีจำนวนเลขคู่และเลขคี่เท่ากัน

ตัวอย่าง

อินพุต: arr[] = {1, 3, 5, 7, 8, 3, 2}

เอาต์พุต: 4

คำอธิบาย: {7,8}, {8,3}, {3,2}, {7,8,3,2}

อินพุต: arr[] = {2, 4, 6}

เอาต์พุต: 0

คำอธิบาย: ทุกตัวเป็นเลขคู่

แนวทางการแก้ปัญหา (Efficient O(n))

ใช้ตัวแปร temp แทนความต่าง (odd - even): เจอคี่ +1, เจอคู่ -1
เมื่อค่า temp ซ้ำกัน แสดงว่าระหว่างจุดทั้งสองมี odd-even เท่ากัน
ใช้ 2 array นับ frequency: arr_1 สำหรับ temp ≥ 0, arr_2 สำหรับ temp < 0

การนำไปใช้ (Implementation)

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

int Sub_even_odd(int arr[], int size) {
    int count = 0;
    int temp = 0;
    int arr_1[size + 1] = {0};
    int arr_2[size + 1] = {0};
    arr_1[0] = 1; // เริ่มต้น temp = 0
    
    for (int i = 0; i < size; i++) {
        if (arr[i] & 1) temp++; // odd
        else temp--;            // even
        
        if (temp < 0) {
            count += arr_2[-temp];
            arr_2[-temp]++;
        } else {
            count += arr_1[temp];
            arr_1[temp]++;
        }
    }
    return count;
}

int main() {
    int arr[] = {3, 4, 6, 1, 2, 4, 10, 42};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Count of subarrays with same even and odd elements are: " << Sub_even_odd(arr, size);
    return 0;
}

เอาต์พุต

Count of subarrays with same even and odd elements are: 4