양의 정수 배열이 제공됩니다. 목표는 각 하위 배열에 동일한 수의 짝수 및 홀수 요소가 포함되도록 배열에서 숫자의 하위 배열을 찾는 것입니다. 배열이 { 1,2,3,4 }인 경우. 그러면 하위 배열은 {1,2}, {2,3}, {3,4}, {1,2,3,4}가 됩니다. 이러한 하위 배열의 개수는 4입니다.
예를 들어 이해하자
입력 - arr[] ={1,3,5,7,8,3,2 };
출력 − 짝수 및 홀수 요소가 동일한 하위 배열의 수는 − 4
설명 − 하위 배열은 − { 7,8 }, {8,3} {3,2}, {7,8,3,2}
입니다.입력 - arr[] ={2,4,6 };
출력 − 짝수 및 홀수 요소가 동일한 하위 배열의 개수는 − 0
설명 − 모든 요소가 짝수입니다.
아래 프로그램에서 사용한 접근 방식은 다음과 같습니다.
이 접근 방식에서 변수 temp를 배열 요소(초기 0) 간의 차이로 사용하고 arr[i]가 홀수이면 1씩 증가시키고 arr[i]가 짝수이면 1만큼 감소시킵니다. temp 값이 반복되면 이러한 인덱스 사이에 동일한 수의 짝수-홀수를 가진 하위 배열이 있어야 합니다. 온도는 양수일 수도 있고 음수일 수도 있습니다. 양수 차이의 빈도에 대해 두 개의 해시 배열 arr_1[size+1]을, 음수 차이의 빈도에 대해 arr_2[size+1]을 사용합니다.
각 차이 temp<0에 대해 count에 arr_1[-temp]의 빈도를 추가합니다. [ -(-temp) ]는 양수 인덱스를 제공합니다.
각 차이 temp> 0에 대해 count에 arr_2[temp]의 빈도를 추가합니다. 동일한 차이 값의 모든 발생은 하위 배열의 일부가 됩니다. 이 주파수를 1씩 업데이트하십시오.
Arr[] = { 1,3,5,7,8,3,2 } 0 −
에서 시작하는 온도 값1,2,3,4,3,4,3
arr_1[] { 1,1,1,3,2,0,0,0 } //all differences are positive
arr_2[] { 0,0,0,0,0,0,0,0 } //no difference is negative
Adding arr_1[temp] to count in each iteration gives count=4. 하위 배열은 − { 7,8 }, {8,3} {3,2}, {7,8,3,2}
입니다.-
초기 배열을 arr[]로 사용합니다.
-
함수 Sub_even_odd(int arr[], int size)는 배열과 그 길이를 취하고 동일한 짝수 및 홀수 요소를 가진 하위 배열의 개수를 반환합니다.
-
초기 카운트를 0으로, 변수 temp를 홀수 값을 만나면 증가하고 짝수 값을 만나면 감소하는 변수로 취합니다.
-
temp의 주파수를 저장하기 위해 두 개의 배열 arr_1[] 및 arr_2[]를 사용합니다. 전체 배열이 짝수인 경우 최대 크기+1이 될 수 있는 temp의 양수 값에 대해 arr_1[].
전체 배열이 짝수인 경우 최대 size+1이 될 수 있는 음수 temp 값의 경우 [].
-
for 루프를 사용하여 ar[]를 트래버스합니다.
-
arr[i] &1==1이면 arr[i]가 홀수임을 의미합니다. 증분 온도 그렇지 않으면 온도가 감소합니다.
-
temp<0이면 arr_2[]에서 해당 빈도를 count에 추가합니다. 해당 빈도를 1만큼 증가시킵니다.
-
temp> 0이면 arr_1[]에서 해당 빈도를 계산에 추가합니다. 해당 빈도를 1만큼 증가시킵니다.
-
결국, 우리는 짝수 및 홀수 요소의 수가 동일한 arr[]의 하위 배열 수로 계산했습니다.
-
결과로 카운트를 반환합니다.
예
#include <bits/stdc++.h>
using namespace std;
int Sub_even_odd(int arr[], int size){
int count = 0;
int temp = 0;
int arr_1[size + 1] = {0};
int arr_2[size + 1] = {0};
arr_1[0] = 1;
for (int i = 0; i < size; i++){
if(arr[i] & 1 == 1)
{ temp++; }
else
{ temp--; }
if (temp < 0){
count += arr_2[-temp];
arr_2[-temp]++;
}
else{
count += arr_1[temp];
arr_1[temp]++;
}
}
return count;
}
int main(){
int arr[] = {3, 4, 6, 1, 2, 4, 10, 42};
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Count of subarrays with same even and odd elements are: "<<Sub_even_odd(arr,
size);
return 0;
} 출력
위의 코드를 실행하면 다음과 같은 출력이 생성됩니다 -
Count of subarrays with same even and odd elements are: 4