Đếm mảng con chỉ chứa 0 hoặc chỉ chứa 1 trong mảng nhị phân C++

Cho mảng arr[] chỉ chứa 0 và 1. Đếm tất cả mảng con chỉ toàn 0 hoặc toàn 1 (không trộn lẫn). Ví dụ [1,0,0] → mảng con toàn 0: [0], [0], [0,0] (3); toàn 1: [1] (1).

Ví dụ

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

Đầu vào: arr[] = {1,0,1,0}
Đầu ra: Toàn 0: 2, Toàn 1: 2.

Giải thuật

Duyệt mảng 2 lần: một lần đếm chuỗi 0 liên tiếp, một lần đếm chuỗi 1 liên tiếp. Với mỗi chuỗi dài count, số mảng con là count * (count + 1) / 2. Cộng dồn.

Ví dụ triển khai

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

void sub_zero_one(int arr[], int size) {
    int count_1 = 0, count_0 = 0;
    int temp_1 = 0, temp_0 = 0;
    // Đếm mảng con toàn 1
    for (int i = 0; i < size; i++) {
        if (arr[i] == 1) count_1++;
        else {
            int temp_one_1 = count_1 * (count_1 + 1) / 2;
            temp_1 += temp_one_1;
            count_1 = 0;
        }
    }
    if (count_1) {
        temp_1 += count_1 * (count_1 + 1) / 2;
    }
    // Đếm mảng con toàn 0
    for (int i = 0; i < size; i++) {
        if (arr[i] == 0) count_0++;
        else {
            int temp_one_0 = count_0 * (count_0 + 1) / 2;
            temp_0 += temp_one_0;
            count_0 = 0;
        }
    }
    if (count_0) {
        temp_0 += count_0 * (count_0 + 1) / 2;
    }
    cout << "Subarrays with only 0's are : " << temp_0;
    cout << "\nSubarrays with only 1's are : " << temp_1;
}

int main() {
    int arr[] = {0, 0, 0, 1, 1, 0, 1};
    int size = sizeof(arr) / sizeof(arr[0]);
    sub_zero_one(arr, size);
    return 0;
}

Kết quả

Subarrays with only 0's are : 7
Subarrays with only 1's are : 4