Đếm mảng con có số lượng phần tử chẵn và lẻ bằng nhau trong C++

Cho mảng số nguyên dương. Đếm mảng con có số phần tử chẵn và lẻ bằng nhau. Ví dụ {1,2,3,4} → {1,2}, {2,3}, {3,4}, {1,2,3,4} (4 mảng con).

Ví dụ

Đầu vào: arr[] = {1,3,5,7,8,3,2}
Đầu ra: 4 ({7,8}, {8,3}, {3,2}, {7,8,3,2}).

Đầu vào: arr[] = {2,4,6}
Đầu ra: 0.

Giải thuật (Hiệu quả - Hash chênh lệch)

Giữ biến temp = chênh lệch (số lẻ - số chẵn). Gặp số lẻ → temp++, số chẵn → temp--. Khi temp lặp lại giá trị cũ → tồn tại mảng con giữa 2 vị trí đó có chẵn/lẻ bằng nhau. Dùng 2 mảng đếm tần suất temp dương và âm.

Ví dụ triển khai

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

int Sub_even_odd(int arr[], int size) {
    int count = 0, temp = 0;
    int arr_1[size + 1] = {0}; // temp >= 0
    int arr_2[size + 1] = {0}; // temp < 0
    arr_1[0] = 1;
    for (int i = 0; i < size; i++) {
        if (arr[i] & 1) temp++;
        else temp--;
        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;
}

Kết quả

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