Bitwise AND of numbers containing at least one non-empty subarray written in C++

To solve the problem given an array, we need to find all possible integers that are at least the bitwise AND of a non-empty subarray, e.g. -

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 }

Methods to find solutions

The simple method that can be applied is,

• Find all possible non-empty subarrays.

• When traversing an array, calculate the bitwise AND of each element in the subarray.

• To avoid duplicate values, store all results in a collection.

Example

#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

The above code description

• States that set stores all AND operations result.

• Initialize the "val" variable using INT_MAX because we need to set all bits to 1 for the AND operation.

• The inner loop iterates through all possible subarrays in the i-th index.

• Relates the elements to each other and to itself Perform an AND operation and store it in the result set.

• Print All

Conclusion

In this tutorial, we discussed a simple way to solve this problem, That is, calculate each possible subarray of the AND operation. We also discussed a C program to solve this problem. Also, you can write this code in any other language like Java, C, Python, etc. We hope you found this tutorial helpful.

The above is the detailed content of Bitwise AND of numbers containing at least one non-empty subarray written in C++. For more information, please follow other related articles on the PHP Chinese website!