Chúng ta được cung cấp một mảng arr [] chứa các số nguyên và một biến X. Mục tiêu là đếm tất cả các mảng con của arr [] sao cho mỗi mảng con chỉ chứa các phần tử nhỏ hơn hoặc bằng X. Ví dụ nếu mảng là [1, 2,3] và X =2 thì các mảng con sẽ là [1], [2] và [1,2]
Hãy cho chúng tôi hiểu với các ví dụ.
Đầu vào - arr [] ={4,3,2,1,6}; X =3
Đầu ra - Đếm mảng con có phần tử nhỏ hơn hoặc bằng X là - 6
Giải thích - Các nhóm phụ sẽ -
[3], [2], [1], [3,2], [2,1], [3,2,1]
Đầu vào - arr [] ={3,6,2,7,1,8,5}; X =5
Đầu ra - Số mảng con có phần tử nhỏ hơn hoặc bằng X là - 4
Giải thích - Các nhóm phụ sẽ -
[3], [2], [1], [5]
Cách tiếp cận được sử dụng trong chương trình dưới đây như sau
Chúng tôi đang tạo một mảng nhị phân temp_arr [] có cùng kích thước với mảng ban đầu arr []. Mảng nhị phân này sẽ có 1 nếu arr [i] tương ứng nhỏ hơn hoặc bằng X, khác 0. Bây giờ hãy duyệt qua temp_arr [] và kiểm tra 1’s liên tục (các phần tử nhỏ hơn X trong arr []). Lưu trữ độ dài của mỗi mảng con như vậy trong tạm thời. Đối với một mảng có độ dài tạm thời. Tổng số mảng con sẽ là tạm thời * (tạm thời + 1) / 2. Thêm điều này vào tổng số và tiếp tục cho đến cuối temp_arr [].
-
Lấy mảng arr [] và biến X.
-
Hàm sub_X (int arr [], int size, int x) nhận mảng và x và trả về số lượng các mảng con chỉ có các phần tử nhỏ hơn hoặc bằng x.
-
Lấy nhiệt độ của biến tạm thời và tổng số cuối cùng của các mảng con đó làm số đếm.
-
Lấy một mảng nhị phân temp_arr [] có độ dài giống như arr [].
-
Chúng ta sẽ duyệt qua mảng arr [] bằng vòng lặp for từ i =0 đến i
-
Đối với mỗi phần tử arr [i] <=x, hãy đặt temp_arr [i] =1 khác 0.
-
Traverse temp_arr [] bằng vòng lặp for.
-
Nếu bất kỳ phần tử nào temp_arr [i] ==1. Sau đó duyệt qua bằng cách sử dụng vòng lặp phụ từ chỉ mục hiện tại i cho đến temp_arr [temp_2] (temp_2 =i + 1; temp_2
-
Số lượng mảng con có tất cả 1 sẽ là temp =temp_2-i.
-
Mảng con này có tất cả 1’s có nghĩa là tất cả các phần tử trong arr [i] đều <=x. Tổng số mảng con sẽ là temp_3 =temp * (temp + 1) / 2.
-
Khi kết thúc cả hai lần truyền, số đếm sẽ có tổng số lần đếm của tất cả các mảng con trong arr có các số nhỏ hơn hoặc bằng x.
Ví dụ
#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++){
if (arr[i] <= x){
temp_arr[i] = 1;
}
else{
temp_arr[i] = 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 = 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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of sub-arrays which have elements less than or equal to X are: 3