Bitwise OR ( Array Problem )

help
1

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}

2

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!

3

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

4

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.

5

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:

6

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])).

7

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

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

9

Added explanation in the code.

10

But how exactly are you handling the condition of strictly increasing subsequences?

11

This is my code to the above question.

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

#define ll long long
#define vll vector<ll>
#define vvl vector<vector<ll>>

ll n; 
vll a;

void solve() {
cin >> n;
a.resize(n);

ll x = 0;
for(ll i = 0; i < n; i++) {
    cin >> a[i];
    x |= a[i];
}

vvl dp(n, vll(x + 1, 1e4));
dp[0][a[0]] = a[0]; dp[0][0] = 0;
for(ll i = 1; i < n; i++) {
    dp[i][a[i]] = min(dp[i - 1][a[i]], a[i]);
    for(ll mask = 0; mask <= x; mask++) {
        if(dp[i - 1][mask] != 1e4 && dp[i - 1][mask] < a[i]) {
            dp[i][mask | a[i]] = min(dp[i][mask | a[i]], a[i]);
        }
    }
}

vll ans;

for(ll mask = 0; mask <= x; mask++) {
    bool val = 0;
    for(ll i = 0; i < n; i++) {
        if(dp[i][mask] != 1e4) {
            val = 1; break;
        }
    }
    if(val) ans.push_back(mask);
}

for(auto& i: ans) cout << i << " "; cout << endl;
}

int main() {
  ll test; cin >> test;
  while(test--) {
      solve();
  }
}