Write a code using C++ to find the number of subarrays with odd sums

A subarray is a contiguous part of an array. For example, we consider an array [5, 6, 7, 8], then there are ten non-empty sub-arrays, such as (5), (6), (7), (8), (5, 6), (6, 7), (7,8), (5,6,7), (6,7,8) and (5,6,7,8).

In this guide, we will explain all possible information in C to find the number of subarrays with odd sums. To find the number of sub-arrays of odd sums we can use different methods so here is a simple example -

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

brute force method

By this method we can simply check Is the sum of elements in all sub-arrays even or odd, if it is even we will reject that sub-array and count the sub-array whose sum is odd, this is not an efficient way as the complexity of this code is 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

Description of the above code

A nested loop is used in this code, where the outer loop is used to increment the value of I , I points to each value from the beginning of the array; the inner loop is used to find the subarray starting at position " i " with an odd sum.

Efficient method

In this method we are processing every element starting from the 0th position in the array. If the current element is odd, increment an odd counter and increment an even counter for each even number. If we find an odd number, the values ​​of Even and odd are swapped, since adding an odd number to the subarray changes its parity, and finally a count is added to the result. The complexity of this code is O(n) since we are processing each element.

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

Explanation of the above code

In this code, we check the even/odd number of each element and Increment the even counter for even numbers and increment the odd counter for odd numbers. Additionally, if an odd number is found, we will swap the parity counter values; otherwise, it will change the parity of the subarray. Then add the value of the odd counter to the result variable after each iteration.

Conclusion

In this article we explained how to find the number coercion method from Brute for subarrays with an odd sum, generate each subarray with an odd sum and increment the count. The time complexity of this code is O(n2). An efficient way to do this is to iterate over each element of the array and increment the odd/even counter variable with each odd/even number found, swapping the counters if an odd number is found; the time complexity of this code is O(n). I hope you found this article helpful in understanding the problem and solution.

The above is the detailed content of Write a code using C++ to find the number of subarrays with odd sums. For more information, please follow other related articles on the PHP Chinese website!