AND au niveau du bit de nombres contenant au moins un sous-tableau non vide écrit en C++

Pour résoudre un problème étant donné un tableau, nous devons trouver tous les entiers possibles qui sont au moins le ET au niveau du bit d'un sous-tableau non vide, comme -

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 }

méthodes pour trouver la solution

peuvent être appliquées Le une méthode simple est,

• de trouver tous les sous-tableaux non vides possibles.

• Lorsque vous parcourez un tableau, calculez le ET au niveau du bit de chaque élément du sous-tableau.

• Pour éviter les valeurs en double, stockez tous les résultats dans une collection.

Exemple

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

Output

All possible numbers are: 1 8 3 6 0 2

La description du code ci-dessus

• déclare set pour stocker tous les résultats de l'opération ET.

• Initialisez la variable "val" en utilisant INT_MAX car nous devons définir tous les bits sur 1 pour l'opération AND.

• La boucle interne parcourt tous les sous-tableaux possibles dans le i-ième index

• ET chaque élément les uns avec les autres et avec lui-même et le stocke dans l'ensemble de résultats.

• Imprimer tout

Conclusion

Dans ce tutoriel, nous avons discuté d'un moyen simple de résoudre ce problème, qui consiste à calculer l'opération ET pour chaque sous-tableau possible. Nous avons également discuté des programmes C++ pour résoudre ce problème. De plus, vous pouvez écrire ce code dans n'importe quel autre langage comme Java, C, Python, etc. Nous espérons que vous avez trouvé ce tutoriel utile.

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!