นับ Subarray ที่มีแต่ 0 หรือแต่ 1 ใน Binary Array ใน C++

เราได้รับอาร์เรย์ arr[] ที่มีแต่ 0 และ 1 เท่านั้น เป้าหมายคือนับ subarray ทั้งหมดที่มีแต่ 0 หรือแต่ 1 (ไม่รวมทั้งคู่)

ตัวอย่าง

อินพุต: arr[] = {0, 0, 1, 1, 1, 0}

เอาต์พุต: Subarrays with only 0's: 4, Subarrays with only 1's: 6

คำอธิบาย:

0's: [0], [0], [0], [0,0] (index 0, 1, 5, 0-1)
1's: [1], [1], [1], [1,1], [1,1], [1,1,1] (index 2, 3, 4, 2-3, 3-4, 2-4)

อินพุต: arr[] = {1, 0, 1, 0}

เอาต์พุต: 0's: 2, 1's: 2

แนวทางการแก้ปัญหา

วนลูปอาร์เรย์ 2 รอบ แยกนับ 0 และ 1 ใช้ตัวนับ consecutive count แล้วคำนวณ subarray ด้วยสูตร count × (count + 1) / 2

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

#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;
    
    // นับ subarray ของ 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;
    }
    
    // นับ subarray ของ 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;
}

เอาต์พุต

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