Programming in C++, find the number of subarrays with m odd numbers

If you have ever used C, you must know what subarrays are and how useful they are. As we all know that in C we can solve multiple mathematical problems easily. So, in this article, we will explain how to find the complete information of M odd numbers in C with the help of these subarrays.

In this problem, we need to find a number of subarrays consisting of a given array and integers m, where each subarray contains exactly m odd numbers. Here is a simple example of this approach -

Input : array = { 6,3,5,8,9 }, m = 2
Output : 5
Explanation : Subarrays with exactly 2 odd numbers are
{ 3,5 }, { 6,3,5 }, { 3,5,8 }, { 5,8,9 }, { 6,3,5,8 }, { 3,5,8,9 }

Input : array = { 1,6,3,2,5,4 }, m = 2
Output : 6
Explanation : Subarrays with exactly 2 odd numbers are
{ 1,6,3 }, { 3,2,5 }, { 1,6,3,2 }, { 6,3,2,5 }, { 3,2,5,4 }, { 6,3,2,5,4 }

First approach

In this approach all possible sub-arrays are generated from the given array and each sub-array is checked Whether the array has exactly m odd numbers. This is a simple generation and lookup method with a time complexity of O(n²).

Example

#include <bits/stdc++.h>
using namespace std;
int main (){
    int a[] = { 1, 6, 3, 2, 5, 4 };
    int n = 6, m = 2, count = 0; // n is size of array, m numbers to be find in subarrays,
                              // count is number of subarray with m odd numbers
    for (int i = 0; i < n; i++){ // outer loop to process each element.
        int odd = 0;
        for (int j = i; j < n; j++) {// inner loop to find subarray with m number
            if (a[j] % 2)
                odd++;
            if (odd == m) // if odd numbers become equals to m.
                count++;
        }
    }
    cout << "Number of subarrays with n numbers are: " << count;
    return 0;
}

Output

Number of subarrays with n numbers are: 6

Description of the above code

In this code, we use nested loops to find m odd subarrays , the outer loop is used to increment "i", which will be used to process each element in the array.

The inner loop is used to find subarrays and process elements until the odd counter reaches m, increment the result counter count for each subarray found, and finally print the result stored in the count

Second One approach

Another approach is to create an array to store the "i" number of odd prefixes, process each element, and increment the number of odd numbers each time an odd number is found.

When the number of odd numbers exceeds or equals m, add the number at the (odd - m) position in the prefix array to it.

When the odd number becomes greater than or equal to m, we count the number of subarrays formed until the index and "odd - m" numbers are added to the count variable. After each element is processed, the result is stored in the count variable.

Example

#include <bits/stdc++.h>
using namespace std;
int main (){
    int array[ ] = { 1, 6, 3, 2, 5, 4 };
    int n = 6, m = 2, count = 0, odd = 0, i;
    int prefix_array[n + 1] = { 0 };
    // outer loop to process every element of array
    for (i = 0; i < n; i++){
        prefix_array[odd] = prefix_array[odd] + 1;    // implementing value at odd index in prefix_array[ ]
        // if array element is odd then increment odd variable
        if (array[i] % 2 == 0)
            odd++;
        // if Number of odd element becomes equal or greater than m
        //  then find the number of possible subarrays that can be formed till the index.
        if (odd >= m)
            count += prefix_array[odd - m];
    }
    cout << "Number of subarrays with n numbers are: " << count;
    return 0;
}

Output

Number of subarrays with n numbers are: 6

Explanation of the above code

Initialize arrays and variables with starting values ​​-

int array[ 6 ] = { 1, 6, 3, 2, 5, 4 };
int n = 6, m = 2, count = 0, odd = 0, i;
int prefix_array[n + 1] = { 0 };

Here , we initialize the variable n with the size of the array, m with the number of odd numbers to find, the count with 0 to keep a count of possible subarrays, the odd numbers with 0, and the variable n 0 with a prefix_array of size n 1 .

Understanding Loops

for (i = 0; i < n; i++){
   prefix_array[odd] = prefix_array[odd] + 1;
   if (array[i] % 2 == 0)
      odd++;
      if (odd >= m)
         count += prefix_array[odd - m];
}

In this loop we implement the value at odd index in prefix_array[] and then increment the odd variable if an odd number is found. We find that when odd variables are equal to or greater than m, the number of subarrays can be formed, up to index.

Finally, we print the m odd subarray numbers stored in the count variable and get the output.

Conclusion

In this article, we learned about the method of finding the number of m odd subarrays through two methods-

• Generate each sub-array array and check if there are m odd numbers in it and increment the count for each sub-array found. The time complexity of this code is O(n2).

• Efficient way, iterate through each element of the array and create a prefix array, then use the help of prefix array. The time complexity of this code is O(n).

Hope this article helps you understand the problem and solution.

The above is the detailed content of Programming in C++, find the number of subarrays with m odd numbers. For more information, please follow other related articles on the PHP Chinese website!