# Bitwise OR ( Array Problem )

How can I find out bitwise OR of elements of all possible strictly increasing subsequences present in an array in O(n2) time??

For example:

array = [4,2,4,1]
output = [0,4,2,1,6]

To get Bitwise OR value = 0, you can choose an empty sequence

To get Bitwise OR value = 4 you can choose a subsequence {4}

To get Bitwise OR value=2 you can choose a subsequence {2}

To get Bitwise OR value=1 you can choose a subsequence {1}

To get Bitwise OR value=6 you can choose a subsequence {2,4}

Hey, for an array, the total number of all possible increasing subsequences can be in the order of 2^n

How? Consider a strictly increasing array of size N. Now any subsequence you pick will be strictly increasing and the total number of subsequences in any array of size n is 2^n - 1, so it is impossible to find the bitwise OR of all possible subsequences in O(n^2).

In case you are trying to solve some problem where you feel this is needed, please share the link to the problem so that we can help!

Don’t have link but I was trying to solve this problem:

You are given an array arr of N integers. Now, you can choose any strictly increasing subsequence of the array and calculate the bitwise OR of all the elements of the subsequence. A subsequence can be obtained by deleting several elements (possibly none or all) from the array without changing the order of the remaining elements. A sequence a1, a2, a3…am is called strictly increasing if a1 < a2 < a3 <…< am

Determine all possible different values of p (p>=0) such that there exist a strictly increasing subsequence such that the bitwise OR of all the elements of the subsequence is equal to p.

Example

Assumptions

N=4
arr = [4,2,4,1]

Approach

1. To get p= 0, you can choose an empty sequence

2. To get p= 4 you can choose a subsequence {4}

3. To get p=2 you can choose a subsequence {2}

4. To get p=1 you can choose a subsequence {1}

5. To get p=6 you can choose a subsequence {2,4}

Different values of p will be: 0,1,2,4,6.

Function description

Complete the function solve provided in the editor. This function takes the following 2 parameters and returns the required answer

1. N: Represents the length of the anay

2. arr: Represents the array of length N.

Input format

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button)

The first line contains T denoting the number of test cases T also specifies the number of times you have to run the solve function on a different set of inputs.

For each test case:

The first line contains n denoting the length of the array. The second line contains n space separated integers denoting the elements of arr.

Output format

Print all the different values of p in increasing order in a new line.

Constraints

1≤T≤ 10

1<=N<=10^4

0 ≤ arri ≤ 500

Sample Input:
1
4
3 5 1 5

Sample Output:
0 1 3 5 7

Any approach can time out for the following kind of input.

N = 32
Arr = [1, 2, 4, 8, 16, ..., 2^32]


This sequence has 2^{33} subsequences and the Bitwise-OR of every subsequence is unique. Therefore, you’ll end up having 2^{33} possible values for p, which is not feasible for calculation.

My friend got this question in OT which was taken on Hackerearth platform. That’s why I feel like there should be optimal sol.

Wait!
It is given that arr[i] \le 500. So I guess we can brute-force the answer. The time complexity would be O(N\cdot \text{max}(Arr[i])).

Here’s the code:

CPP
#include <bits/stdc++.h>
using namespace std;

void solve(const vector<int>& arr, const int N) {

int max_possible = 0;
// Bitwise OR of all the elements
// in the array will be the Maximum
for(int i = 0; i < N; i++) {
max_possible |= arr[i];
}

// To store Bitwise OR of
// all possible subsequences
vector<int> ans;

for(int i = 0; i <= max_possible; i++) {
// Check if 'i' can be obtained
// by taking Bitwise OR of a
// subset in Array

int value = 0;

for(int j = 0; j < N; j++) {
if((i & arr[j]) == arr[j]) {
value |= arr[j];
}
}

if(i == value)
ans.push_back(i);
}

for(int i = 0; i < static_cast<int>(ans.size()); i++) {
cout << ans[i] << " \n"[i == static_cast<int>(ans.size()) - 1];
}
}

int main() {

vector<int> arr = {4, 2, 4, 1};
solve(arr, arr.size());

arr = {3, 5, 1, 5};
solve(arr, arr.size());

return 0;
}


Could you explain your approach? Why this will work? It would be a great help.