Écrivez un code en C++ pour trouver le nombre de sous-tableaux avec des sommes impaires

Un sous-tableau est une partie contiguë d'un tableau. Par exemple, on considère un tableau [5, 6, 7, 8], alors il y a dix sous-tableaux non vides, tels que (5), (6), (7), (8), (5, 6 ), (6, 7), (7,8), (5,6,7), (6,7,8) et (5,6,7,8).

Dans ce guide, nous expliquerons toutes les informations possibles pour trouver le nombre de sous-tableaux à sommes impaires en C++. Pour trouver le nombre de sous-tableaux avec des sommes impaires, nous pouvons utiliser différentes méthodes, voici donc un exemple simple -

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

Méthode de la force brute

Par cette méthode, nous pouvons simplement vérifier que la somme des éléments dans tous les sous-tableaux est paire ou impair, si c'est pair nous rejetterons le sous-tableau et calculerons le sous-tableau dont la somme est impaire, ce n'est pas un moyen efficace car la complexité de ce code est O(n²).

Exemple

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

Sortie

Number of subarrays with odd sum : 9

La description du code ci-dessus

Une boucle imbriquée est utilisée dans ce code, où la boucle externe est utilisée pour incrémenter la valeur de I, et I pointe vers chaque valeur du tableau depuis le début ; la boucle interne est utilisée pour trouver un sous-tableau avec une somme impaire commençant à la position " i " .

Méthode efficace

Dans cette méthode, nous traitons chaque élément à partir de la 0ème position du tableau. Si l'élément actuel est impair, incrémentez un compteur impair et incrémentez un compteur pair pour chaque nombre pair. Si nous trouvons un nombre impair, les valeurs de Pair et impair sont inversées, car l'ajout d'un nombre impair au sous-tableau modifie sa parité, et enfin un décompte est ajouté au résultat. La complexité de ce code est O(n) puisque nous traitons chaque élément.

Exemple

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

Sortie

Number of subarrays with odd sum : 9

Explication du code ci-dessus

Dans ce code, nous vérifions le nombre pair/impair de chaque élément et incrémentons le compteur pair pour pair et le compteur impair pour impair. De plus, si un nombre impair est trouvé, nous échangerons les valeurs du compteur de parité ; sinon, cela modifiera la parité du sous-tableau. Ajoutez ensuite la valeur du compteur impair à la variable résultat après chaque itération.

Conclusion

Dans cet article, nous avons expliqué comment trouver la méthode de coercition numérique de Brute pour les sous-tableaux avec une somme impaire, générer chaque sous-tableau avec une somme impaire et incrémenter le nombre. La complexité temporelle de ce code est O(n2). Un moyen efficace de procéder consiste à parcourir chaque élément du tableau et à incrémenter la variable compteur impair/pair avec chaque nombre impair/pair trouvé, en échangeant les compteurs si un nombre impair est trouvé, la complexité temporelle de ce code est O( n). J'espère que vous avez trouvé cet article utile pour comprendre le problème et la solution.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!