정수 배열 arr[]이 제공됩니다. 또한 두 개의 숫자 A와 B. 목표는 A와 B의 발생이 모두 동일하도록 arr[]의 모든 하위 배열을 계산하는 것입니다. 배열이 [1,2,3]이고 A가 1이고 B가 2인 경우 하위 배열은 [3], [1,2], [1,2,3]입니다.
예를 들어 이해합시다.
입력 - arr[] ={ 2, 2, 1, 1, 1, 5 }; A=1, B=5
출력 − 동일한 번호를 갖는 하위 배열의 수입니다. 주어진 두 요소의 발생 횟수는 -4
설명 − 하위 배열은 − [2], [2], [2,2], [1,5]입니다. 처음 세 개는 1과 5가 0번 발생하고 마지막 세 개는 둘 다 1번 발생합니다.
입력 - arr[] ={ 5,3,7,5,3 }; A=1, B=2
출력 − 동일한 번호를 갖는 하위 배열의 수입니다. 주어진 두 요소의 발생 횟수는 -15
입니다.설명 − 하위 배열은 − (1과 2가 0번 발생함)
[5], [3], [7], [5], [3] - 5 [5,3], [3,7], [7,5], [5,3] - 4 [5,3,7], [3,7,5], [7,5,3] - 3 [5,3,7,5], [3,7,5,3] - 2 [5,3,5,7,5] - 1
1과 2 모두 발생하지 않은 총 15개의 하위 배열(0회 발생).
아래 프로그램에서 사용한 접근 방식은 다음과 같습니다.
가능한 모든 하위 배열을 생성하기 위해 두 개의 for 루프를 사용하여 배열을 탐색합니다. i=0에서 i<=size-1로, j=i에서 j<=size-1로. 형성된 하위 배열은 arr[i]에서 arr[j] 사이에 있습니다. 각 부분배열에서 A와 B의 빈도를 셉니다. 같으면 카운트를 증가시킵니다.
-
숫자의 배열 arr[]를 가져옵니다.
-
함수 sub_EqualOccurrence(int arr[], int size, int A, int B)는 배열을 취하고 동일한 번호를 가진 하위 배열의 수를 반환합니다. A와 B.
-
초기 카운트를 0으로 합니다.
-
i=0에서 i<=size-1까지 및 j=0에서 j<=size-1까지 두 개의 for 루프를 사용하여 배열을 탐색합니다.
-
두 개의 변수 total_A, total_B를 하위 배열 arr[i]에서 arr[j]까지의 A와 B의 수에 대해 0으로 사용합니다.
-
arr[j]를 A 및 B와 비교합니다. arr[j]가 A 또는 B이면 각 개수( total_A 또는 total_B)를 증가시킵니다.
-
total_A==total_B인 경우. 증분 카운트. (하위 배열은 요소와 동일한 수의 A와 B를 가집니다.)
-
두 루프의 끝에서 결과로 count를 반환합니다.
예시
#include <bits/stdc++.h>
using namespace std;
int sub_EqualOccurrence(int arr[], int size, int A, int B){
int count = 0;
for (int i = 0; i <= size - 1; i++){
int total_A = 0;
int total_B = 0;
for (int j = i; j <= size - 1; j++){
if (arr[j] == A){
total_A++;
}
else if (arr[j] == B){
total_B++;
}
if(total_A == total_B){
count++;
}
}
}
return count;
}
// Driver code
int main(){
int arr[] = { 2, 3, 1, 1, 4, 5 };
int size = sizeof(arr) / sizeof(arr[0]);
int A = 1, B = 5;
cout<<"Count of subarrays with equal number of occurrences of two given elements are: "<<sub_EqualOccurrence(arr, size, A, B);
return (0);
} 출력
위의 코드를 실행하면 다음 출력이 생성됩니다 -
Count of subarrays with equal number of occurrences of two given elements are: 5