하위 배열은 배열의 연속적인 부분입니다. 예를 들어 배열 [5, 6, 7, 8]을 고려하면 (5), (6), (7), (8), (5, 6), (6)과 같이 비어 있지 않은 10개의 하위 배열이 있습니다. ,7), (7,8), (5,6,7), (6,7,8) 및 (5,6,7,8).
이 가이드에서는 C++에서 합이 홀수인 부분배열의 수를 찾기 위해 가능한 모든 정보를 설명합니다. 홀수 합을 가진 하위 배열의 수를 찾기 위해 다른 접근 방식을 사용할 수 있으므로 여기에 간단한 예가 있습니다.
Input : array = {9,8,7,6,5}
Output : 9
Explanation :
Sum of subarray -
{9} = 9
{7} = 7
{5} = 5
{9,8} = 17
{8,7} = 15
{7,6} = 13
{6,5} = 11
{8,7,6} = 21
{9,8,7,6,5} = 35 무차별 대입 접근
이 접근 방식을 사용하면 모든 하위 배열의 요소 합이 짝수인지 홀수인지 간단히 확인할 수 있습니다. 짝수이면 해당 하위 배열을 거부하고 합계가 홀수인 하위 배열을 계산합니다. 이 코드의 복잡성이 O이므로 효율적인 접근 방식이 아닙니다. (n 2 ).
예시
#include <bits/stdc++.h>
using namespace std;
int main(){
int n=5, temp = 0;
int a[n-1] = { 9,8,7,6,5 } ; // declaring our array.
int cnt = 0; // counter variable.
for(int i = 0; i < n; i++){
temp = 0; // refreshing our temp sum.
for(int j = i; j < n; j++){ // this loop will make our subarrays starting from i till n-1.
temp = temp + a[j];
if( temp % 2 == 1 )
cnt++;
}
}
cout << "Number of subarrays with odd sum : " << cnt << "\n";
return 0;
} 출력
Number of subarrays with odd sum : 9
위 코드 설명
중첩 루프는 I 값을 증가시키는 데 외부 루프가 사용되는 이 코드에서 사용됩니다. 내부 루프는 " i " 위치에서 시작하는 하위 배열을 찾는 데 사용됩니다. 합이 홀수입니다.
효율적인 접근
이 접근 방식에서는 배열의 0번째 위치부터 모든 요소를 처리합니다. 현재 요소가 홀수이면 홀수 카운터를 늘리고 모든 짝수에 대해 짝수 카운터를 늘립니다. 홀수를 찾으면 하위 배열에 홀수를 추가하면 패리티가 변경되고 최종적으로 결과에 개수가 추가되기 때문에 짝수와 홀수 값을 교환합니다. 이 코드의 복잡성은 모든 요소를 처리하므로 O(n)입니다.
예시
#include <bits/stdc++.h>
using namespace std;
int main(){
int odd = 0, even = 0, result = 0,n=5,i,temp;
int arr[ n-1 ] = { 9,8,7,6,5}; // initialising the array
// for loop for processing every element of array
for ( i = 0 ; i < n ; i ++ ) {
if ( arr[ i ] % 2 == 0 ) {
even++;
} else {
// swapping even odd values
temp = even;
even = odd;
odd = temp + 1;
}
result += odd;
}
cout << "Number of subarrays with odd sum : " << result;
} 출력
Number of subarrays with odd sum : 9
위 코드 설명
이 코드에서 우리는 짝수/홀수에 대한 모든 요소를 확인하고 짝수에 대해 짝수 카운터를 증가시키고 홀수에 대해 홀수 카운터를 증가시킵니다. 또한 홀수가 발견되면 홀수-짝수 카운터 값을 교환합니다. 그렇지 않으면 하위 배열의 패리티가 변경됩니다. 그런 다음 모든 반복 후에 결과 변수에 홀수 카운터 값을 추가합니다.
결론
이 기사에서는 합이 홀수인 모든 하위 배열을 생성하고 개수를 증가시키는 무차별 대입 방식에서 합이 홀수인 하위 배열의 수를 찾는 방법을 설명했습니다. 이 코드의 시간 복잡도는 O(n2)입니다. 효율적인 접근 방식은 배열의 각 요소를 살펴보고 발견된 모든 홀수/짝수로 홀수/짝수 카운터 변수를 증가시키고 홀수가 발견되면 카운터를 교체하는 것입니다. 이 코드의 시간 복잡도는 O(n)입니다. 이 문서가 문제와 솔루션을 이해하는 데 도움이 되기를 바랍니다.