C++를 사용하여 합계가 홀수인 하위 배열의 수를 찾는 코드를 작성하세요.

하위 배열은 배열의 연속된 부분입니다. 예를 들어 배열 [5, 6, 7, 8]을 고려하면 (5), (6), (7), (8), (5, 6)과 같이 비어 있지 않은 하위 배열 10개가 있습니다. ), (6,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²)이므로 이는 효율적인 방법이 아닙니다.

Example

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

Output

Number of subarrays with odd sum : 9

위의 코드 설명

이 코드에서는 중첩 루프가 사용됩니다. 여기서 외부 루프는 I의 값을 증가시키는 데 사용되며 I는 배열의 시작 부분부터 각 값을 가리킵니다. ; 내부 루프는 " i " 위치에서 시작하는 홀수 합계를 갖는 하위 배열을 찾는 데 사용됩니다.

효율적인 방법

이 방법에서는 배열의 0번째 위치부터 모든 요소를 ​​처리합니다. 현재 요소가 홀수이면 홀수 카운터를 늘리고 각 짝수에 대해 짝수 카운터를 증가시킵니다. 홀수를 찾으면 하위 배열에 홀수를 추가하면 패리티가 변경되고 마지막으로 결과에 개수가 추가되므로 짝수와 홀수 값이 교환됩니다. 이 코드의 복잡도는 각 요소를 처리하기 때문에 O(n)입니다.

Example

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

Output

Number of subarrays with odd sum : 9

위 코드 설명

이 코드에서는 각 요소의 짝수/홀수를 확인하고 짝수에는 짝수 카운터, 홀수에는 홀수 카운터를 증가시킵니다. 또한 홀수가 발견되면 패리티 카운터 값을 교환하고, 그렇지 않으면 하위 배열의 패리티를 변경합니다. 그런 다음 각 반복 후에 홀수 카운터의 값을 결과 변수에 추가합니다.

결론

이 기사에서는 합이 홀수인 하위 배열에 대해 Brute에서 숫자 강제 변환 방법을 찾고, 합이 홀수인 각 하위 배열을 생성하고 개수를 늘리는 방법을 설명했습니다. 이 코드의 시간 복잡도는 O(n2)입니다. 이를 수행하는 효율적인 방법은 배열의 각 요소를 반복하고 발견된 각 홀수/짝수에 대해 홀수/짝수 카운터 변수를 증가시키고, 홀수가 발견되면 카운터를 교체하는 것입니다. 이 코드의 시간 복잡도는 O( N). 이 글이 문제와 해결책을 이해하는 데 도움이 되기를 바랍니다.

위 내용은 C++를 사용하여 합계가 홀수인 하위 배열의 수를 찾는 코드를 작성하세요.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!