Schreiben Sie mit C++ einen Code, um die Anzahl der Unterarrays mit ungeraden Summen zu ermitteln

Ein Subarray ist ein zusammenhängender Teil eines Arrays. Betrachten wir beispielsweise ein Array [5, 6, 7, 8], dann gibt es zehn nicht leere Unterarrays, wie zum Beispiel (5), (6), (7), (8), (5, 6). ), (6, 7), (7,8), (5,6,7), (6,7,8) und (5,6,7,8).

In diesem Leitfaden erklären wir alle möglichen Informationen, um die Anzahl der Subarrays mit ungeraden Summen in C++ zu ermitteln. Um die Anzahl der Unterarrays mit ungeraden Summen zu ermitteln, können wir verschiedene Methoden verwenden. Hier ist ein einfaches Beispiel:

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-Methode

Mit dieser Methode können wir einfach überprüfen, ob die Summe der Elemente in allen Unterarrays gerade ist oder ungerade, wenn es gerade ist, lehnen wir das Unterarray ab und berechnen das Unterarray, dessen Summe ungerade ist. Dies ist keine effiziente Methode, da die Komplexität dieses Codes O(n²) ist.

Beispiel

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

Ausgabe

Number of subarrays with odd sum : 9

Die obige Codebeschreibung

In diesem Code wird eine verschachtelte Schleife verwendet, wobei die äußere Schleife zum Erhöhen des Werts von I verwendet wird und I von Anfang an auf jeden Wert im Array zeigt ; die innere Schleife wird verwendet, um ein Subarray mit ungerader Summe beginnend an Position " i " zu finden.

Effiziente Methode

Bei dieser Methode verarbeiten wir jedes Element ab der 0. Position im Array. Wenn das aktuelle Element ungerade ist, erhöhen Sie einen ungeraden Zähler und einen geraden Zähler für jede gerade Zahl. Wenn wir eine ungerade Zahl finden, werden die Werte von Even und Odd vertauscht, da das Hinzufügen einer ungeraden Zahl zum Subarray seine Parität ändert, und schließlich wird dem Ergebnis eine Zählung hinzugefügt. Die Komplexität dieses Codes beträgt O(n), da wir jedes Element verarbeiten.

Beispiel

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

Ausgabe

Number of subarrays with odd sum : 9

Erklärung des obigen Codes

In diesem Code prüfen wir die gerade/ungerade Zahl jedes Elements und erhöhen den geraden Zähler für gerade und den ungeraden Zähler für ungerade. Wenn außerdem eine ungerade Zahl gefunden wird, vertauschen wir die Paritätszählerwerte; andernfalls ändert sich die Parität des Subarrays. Fügen Sie dann nach jeder Iteration den Wert des ungeraden Zählers zur Ergebnisvariablen hinzu.

Fazit

In diesem Artikel haben wir erklärt, wie man die Zahlenzwangsmethode von Brute für Subarrays mit einer ungeraden Summe findet, jedes Subarray mit einer ungeraden Summe generiert und die Anzahl erhöht. Die zeitliche Komplexität dieses Codes beträgt O(n2). Eine effiziente Möglichkeit, dies zu tun, besteht darin, jedes Element des Arrays zu durchlaufen und die ungerade/gerade Zählervariable mit jeder gefundenen ungeraden/geraden Zahl zu erhöhen und die Zähler auszutauschen, wenn eine ungerade Zahl gefunden wird. Die zeitliche Komplexität dieses Codes beträgt O(; N). Ich hoffe, dass Ihnen dieser Artikel dabei geholfen hat, das Problem und die Lösung zu verstehen.

Das obige ist der detaillierte Inhalt vonSchreiben Sie mit C++ einen Code, um die Anzahl der Unterarrays mit ungeraden Summen zu ermitteln. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!