C++에서 1과 0의 수가 같은 부분배열의 수 세기

0과 1만 포함하는 배열 arr[]이 제공됩니다. 목표는 0과 1의 발생이 모두 같도록 arr[]의 모든 하위 배열을 계산하는 것입니다. 배열이 [1,0,0]이면 하위 배열은 [1,0]만 됩니다.

예를 들어 이해합시다.

입력 - arr[] ={ 0, 0, 1, 1, 1, 0 };

출력 − 1과 0이 같은 하위 배열의 개수는 − 4입니다.

설명 − Subaarays는 −

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].

입력 - arr[] ={ 0, 1, 1, 1, 1 };

출력 − 1과 0의 수가 같은 하위 배열의 개수는 − 1

설명 − 하위 배열은 − arr[0 ~ 1] =[0,1]

아래 프로그램에서 사용한 접근 방식은 다음과 같습니다.

가능한 모든 하위 배열을 생성하기 위해 두 개의 for 루프를 사용하여 배열을 탐색합니다. i=0에서 i<=size-1로, j=i에서 j<=size-1로. 형성된 하위 배열은 arr[i]에서 arr[j] 사이에 있습니다. 각 하위 배열에서 0과 1의 빈도를 계산합니다. 같으면 카운트를 증가시킵니다.

• 숫자의 배열 arr[]를 가져옵니다.

• 함수 sub_zeroes_ones(int arr[], int size)는 배열을 취하고 동일한 번호를 가진 하위 배열의 수를 반환합니다. 0과 1 중.

• 초기 카운트를 0으로 합니다.

• i=0에서 i<=size-1까지 및 j=0에서 j<=size-1까지 두 개의 for 루프를 사용하여 배열을 탐색합니다.

• arr[i]에서 arr[j]까지의 하위 배열에서 0과 1의 수에 대해 total_0이라는 두 개의 변수 total_1을 0으로 사용합니다.

• arr[j]를 0 및 1과 비교합니다. arr[j]가 0 또는 1이면 각 개수( total_0 또는 total_1)를 증가시킵니다.

• total_0==total_1인 경우. 증분 카운트. (하위 배열은 요소와 동일한 수의 0과 1을 갖습니다.)

• 두 루프의 끝에서 결과로 count를 반환합니다.

예시

#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);
}

출력

위의 코드를 실행하면 다음 출력이 생성됩니다 -

Count of subarrays with equal number of 1’s and 0’s are: 4