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

Task

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. :sweat_smile:

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.

Added explanation in the code.