นับ Sub-array ที่มีองค์ประกอบน้อยกว่าหรือเท่ากับ X ใน C++

เราได้รับอาร์เรย์ arr[] และตัวแปร X เป้าหมายคือนับ subarray ทั้งหมดที่องค์ประกอบทุกตัวมีค่าน้อยกว่าหรือเท่ากับ X

ตัวอย่าง

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

เอาต์พุต: 6

คำอธิบาย: Subarrays: [3], [2], [1], [3,2], [2,1], [3,2,1]

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

เอาต์พุต: 4

คำอธิบาย: Subarrays: [3], [2], [1], [5]

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

1. สร้าง binary array temp_arr[] ขนาดเท่าเดิม: 1 ถ้า arr[i] <= X, มิฉะนั้น 0
2. หา consecutive 1's ใน temp_arr[]
3. สำหรับแต่ละกลุ่มความยาว temp จำนวน subarray = temp × (temp + 1) / 2
4. รวมทั้งหมด

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

#include <iostream>
using namespace std;

int sub_X(int arr[], int size, int x) {
    int count = 0, temp = 0;
    int temp_arr[size];
    
    for (int i = 0; i < size; i++) {
        temp_arr[i] = (arr[i] <= x) ? 1 : 0;
    }
    
    for (int i = 0; i < size; i++) {
        if (temp_arr[i] == 1) {
            int temp_2;
            for (temp_2 = i + 1; temp_2 < size; temp_2++) {
                if (temp_arr[temp_2] != 1) break;
            }
            temp = temp_2 - i;
            int temp_3 = temp * (temp + 1) / 2;
            count += temp_3;
            i = temp_2;
        }
    }
    return count;
}

int main() {
    int arr[] = {2, 6, 1, 10, 5, 3};
    int x = 4;
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Count of sub-arrays which have elements less than or equal to X are: " << sub_X(arr, size, x);
    return 0;
}

เอาต์พุต

Count of sub-arrays which have elements less than or equal to X are: 3