Đếm các mảng con có số lượng 1 và 0 bằng nhau trong C ++

Chúng tôi được cung cấp một mảng arr [] chỉ chứa 0 và 1. Mục đích là để đếm tất cả các mảng con của arr [] sao cho số lần xuất hiện của 0 và 1 là bằng nhau. Nếu mảng là [1,0,0] .Subarray sẽ chỉ là [1,0].

Hãy cho chúng tôi hiểu với các ví dụ.

Đầu vào - arr [] ={0, 0, 1, 1, 1, 0};

Đầu ra - Số lượng các mảng con có số lượng bằng nhau của 1 và 0 là - 4

Giải thích - Các nhóm phụ sẽ -

arr[0 to 3] = [0,0,1,1],
arr[1 to 2] = [0,1],
arr[4 to 5] =[1,0],
Arr[0 to 5] =[0,0,1,1,1,0].

Đầu vào - arr [] ={0, 1, 1, 1, 1};

Đầu ra - Số lượng các mảng con có số lượng bằng nhau của 1 và 0 là - 1

Giải thích - Các tham số con sẽ là - arr [0 đến 1] =[0,1]

Cách tiếp cận được sử dụng trong chương trình dưới đây như sau

Chúng tôi sẽ duyệt qua mảng bằng cách sử dụng hai vòng lặp for để tạo ra tất cả các mảng con có thể. Từ i =0 đến i <=size-1 và j =i đến j <=size-1. Các mảng con được hình thành sẽ nằm giữa arr [i] đến arr [j]. Đếm tần số 0 và 1 trong mỗi mảng con. Nếu bằng nhau thì hãy tăng số lượng.

• Lấy một mảng [] số.

• Hàm sub_zeroes_ones (int arr [], int size) nhận mảng và trả về số lượng các mảng con có số bằng nhau. trong tổng số 0 và 1.

• Lấy số lượng ban đầu là 0.

• Chúng tôi sẽ duyệt qua mảng bằng cách sử dụng hai vòng lặp for từ i =0 đến i <=size-1 và j =0 đến j <=size-1.

• Lấy hai biến total_0, total_1 là 0 cho số lượng của 0 và 1 trong mảng con arr [i] thành arr [j].

• So sánh arr [j] với 0 và 1. Nếu arr [j] bằng 0 hoặc 1 thì số lượng tương ứng tăng dần (tổng_0 hoặc tổng_1).

• Nếu total_0 ==total_1. Số lượng tăng dần. (mảng con có cùng số phần tử là 0 và 1).

• Ở cuối cả hai vòng, kết quả trả về là số lượng.

Ví dụ

#include <bits/stdc++.h>
using namespace std;
int sub_zeroes_ones(int arr[], int size){
   int count = 0;
   for (int i = 0; i <= size - 1; i++){
      int total_0 = 0;
      int total_1 = 0;
      for (int j = i; j <= size - 1; j++){
         if (arr[j] == 0){
            total_0++;
         }
         else if (arr[j] == 1){
            total_1++;
         }
         if(total_0 == total_1){
            count++;
         }
      }
   }
   return count;
}
int main(){
   int arr[] = {0, 1, 1, 0, 0};
   int size = sizeof(arr)/sizeof(arr[0]);
   cout<<"Count of subarrays with equal number of 1’s and 0’s are: "<<sub_zeroes_ones(arr, size);
}

Đầ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 subarrays with equal number of 1’s and 0’s are: 4