0과 1만 포함하는 배열 arr[]이 제공됩니다. 목표는 각 하위 배열에 0만 포함하거나 둘 다 포함하지 않는 1만 포함하도록 arr[]의 모든 하위 배열을 계산하는 것입니다. 배열이 [1,0,0]인 경우 하위 배열은 0의 경우에만 [0], [0], [0,0]이고 1의 경우에만 [1]입니다.
예를 들어 이해합시다.
입력 - arr[] ={ 0, 0, 1, 1, 1, 0 };
출력 − 0만 있는 하위 배열:4 1만 있는 하위 배열:6
설명 − Subaarays는 −
For all 0’s: [0], [0], [0], [0,0]. Total 4 ( arr[0], arr[1], arr[5], arr[0-1] ) For all 1’s: [1], [1], [1], [1,1], [1,1], [1,1,1]. Total 6 ( arr[2], arr[2], arr[4], arr[2-3], arr[3-4], arr[2-4] )
입력 - arr[] ={ 1,0,1,0 };
출력 − 0만 있는 하위 배열:2 1만 있는 하위 배열:2
설명 − Subaarays는 −
For all 0’s: [0], [0]. Total 2 ( arr[1], arr[3] ) For all 1’s: [1], [1]. Total 2 ( arr[0], arr[2] )
아래 프로그램에서 사용한 접근 방식은 다음과 같습니다.
0과 1만 있는 하위 배열을 별도로 계산하기 위해 배열을 두 번 탐색합니다. 두 개의 카운터 count_0 및 count_1을 사용하여 배열에 연속 0과 1의 개수를 저장합니다. 이러한 각 개수에 대해 가능한 하위 배열은 count_0*(count_0+1)/2이고 count_1의 경우에도 유사합니다.
배열의 끝에 도달할 때까지 total_0 count에 이것을 추가합니다. 1에 대해 유사한 과정을 수행합니다.
-
숫자의 배열 arr[]를 가져옵니다.
-
sub_zero_one(int arr[], int size) 함수는 배열을 받아 0만 있는 하위 배열의 개수와 1만 있는 하위 배열의 개수를 반환합니다.
-
하위 배열의 경우 초기 개수를 temp_0 및 temp_1로 사용합니다.
-
0과 1의 임시 연속 카운트를 count_0 및 count_1로 취합니다.
-
for 루프를 사용하여 i=0에서 I
-
현재 요소가 0이면 count_0을 증가시킵니다.
-
그렇지 않은 경우 count_0이 0인 모든 가능한 하위 배열을 temp_one_0=count*(count+1)/2로 계산합니다.
-
지금까지 모두 0이 발견된 하위 배열에 대해 이전 temp_0에 이것을 추가합니다.
-
count_1, temp_one_1 및 temp_1과 같은 변수를 사용하여 for 루프를 사용하여 유사한 프로세스를 수행합니다.
-
두 탐색이 모두 끝나면 temp_0과 temp_1은 모두 0과 모두 1을 갖는 arr 내의 모든 하위 배열에 대한 각각의 카운트를 갖습니다.
예시
#include <bits/stdc++.h>
using namespace std;
void sub_zero_one(int arr[], int size){
int count_1 = 0;
int count_0 = 0;
int temp_1 = 0;
int temp_0 = 0;
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_1 + temp_one_1;
count_1 = 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_0 + temp_one_0;
count_0 = 0;
}
}
if (count_1){
int temp_one_1 = (count_1) * (count_1 + 1) / 2;
temp_1 = temp_1 + temp_one_1;
}
if (count_0){
int temp_one_0 = (count_0) * (count_0 + 1) / 2;
temp_0 = temp_0 + temp_one_0;
}
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