Bitweises UND von Zahlen, die mindestens ein nicht leeres Subarray enthalten, geschrieben in C++

Um ein Problem mit einem gegebenen Array zu lösen, müssen wir alle möglichen ganzen Zahlen finden, die mindestens das bitweise UND eines nichtleeren Unterarrays sind, zum Beispiel -

Input : nums[ ] = { 3, 5, 1, 2, 8 }
Output : { 2, 5, 0, 3, 8, 1 }
Explanation:
2 is the bitwise AND of subarray {2},
5 is the bitwise AND of subarray {5},
0 is the bitwise AND of subarray {1, 2}, {2, 8} and {1, 2, 8},
3 is the bitwise AND of subarray {3},
8 is the bitwise AND of subarray {8},
1 is the bitwise AND of subarray {1}, {3, 5} and {3, 5, 1}.

Input : nums[ ] = { 2, 6, 3, 8, 1 }
Output: { 1, 8, 3, 6, 2, 0 }

Methoden zur Lösungsfindung

können angewendet werden Die einfache Methode besteht darin,

• alle möglichen nicht leeren Subarrays zu finden.

• Berechnen Sie beim Durchlaufen eines Arrays das bitweise UND jedes Elements im Subarray.

• Um doppelte Werte zu vermeiden, speichern Sie alle Ergebnisse in einer Sammlung.

Beispiel

#include <bits/stdc++.h>
using namespace std;
int main(){
    int arr[] ={ 2, 6, 3, 8, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    // Declaring set to store result of each AND operation.
    unordered_set<int> result;
    int val;
    // nested loops to traverse through all the possible non empty subarrays.
    for (int i = 0; i < n; ++i){
        for (int j = i, val = INT_MAX; j < n; ++j){
            val = val & arr[j];
            // storing result of AND operation
            result.insert(val);
        }
    }
    cout << "All possible numbers are: ";
    // printing all the values of set.
    for (auto i = result.begin(); i != result.end();i++)
        cout << *i << " ";
    return 0;
}

Ausgabe

All possible numbers are: 1 8 3 6 0 2

Die obige Codebeschreibung

• deklariert, dass alle Ergebnisse der UND-Operation gespeichert werden sollen.

• Initialisieren Sie die Variable „val“ mit INT_MAX, da wir für die UND-Verknüpfung alle Bits auf 1 setzen müssen.

• Die innere Schleife durchläuft alle möglichen Unterarrays im i-ten Index.

• Verknüpft jedes Element miteinander und mit sich selbst und speichert es im Ergebnissatz.

• Alles drucken

Fazit

In diesem Tutorial haben wir eine einfache Möglichkeit zur Lösung dieses Problems besprochen, nämlich die UND-Operation für jedes mögliche Unterarray zu berechnen. Wir haben auch C++-Programme zur Lösung dieses Problems besprochen. Sie können diesen Code auch in jeder anderen Sprache wie Java, C, Python usw. schreiben. Wir hoffen, dass Sie dieses Tutorial hilfreich fanden.

Das obige ist der detaillierte Inhalt vonBitweises UND von Zahlen, die mindestens ein nicht leeres Subarray enthalten, geschrieben in C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!