Last Updated: 23 Nov, 2020
Count distinct Bitwise OR of all subarrays
Easy
Asked in companies
You are given an array consisting of N positive integers, your task is to count the number of distinct possible values that can be obtained by taking the bitwise OR of the elements of all possible subarrays of the given array
Note:
1) A subarray is a part of the array which is contiguous (i.e. elements in the original array occupy consecutive positions) and inherently maintains the order of elements. For example, the subarrays of the array {1, 2, 3} are {1}, {1, 2}, {1, 2, 3}, {2}, {2, 3}, and {3}.
2) Bitwise OR operation takes two numbers and performs OR operation on every bit of those two numbers. For example, consider two numbers 2 and 3 their bitwise OR will be 3. Because the binary representation of 2 is 10 and the binary representation of 3 is 11. And OR of 10 and 11 will be 11 which evaluates to 3.
3) The array may contain duplicate elements.
Input Format:
The first line of the input contains an integer T denoting the number of test cases.
The first line of each test case contains an integer N, denoting the size of the array.
The second line of each test case contains N space-separated integers, representing the elements of the array.
Output Format:
The only line of output of each test case consists of an integer, the count of distinct possible values of bitwise OR of all the subarrays.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 100
1 <= N <= 10^5
1 <= ARR[i] <= 10^9
Time Limit : 1sec
Approaches
- The most obvious brute force approach would be to run a nested loop to make all possible subarrays of the given array and store the bitwise OR and at the end count the distinct OR values. We can also make use of the set and insert all the OR values in the set as it stores distinct values only and at the end, we can return the size of the set as the answer.
- We run the outer loop(i) through all the elements of the array:
- Now we run a nested loop(j) starting from ‘i’ up to the end of the array( to traverse over all subarrays starting with the element at index ‘i’), and we maintain a variable var to store the calculated OR value and we initialize this variable(var) to 0.
- As we traverse through the nested loop we keep on doing OR of the element being traversed with the variable var and update the value of the variable var to this new value and insert it into the set.
- After coming out of the above loop we can return the size of the set, as our set will contain all the distinct OR values.
- We know that 1 OR 0 = 1 OR 1 = 1. Thus we can conclude that is some bit is set in some number then no matter what element is ORed with this number that bit will always be set. This fact will help us reduce the time complexity from quadratic to linear.
- In the previous approach we are running a nested loop to generate all the subarrays and then calculate their bitwise OR, basically what we are doing is calculating the value of biwiseOR(i,j) = array[i] | array[i+1]|array[i+2]|....|array[j]. Then we increase j and calculate bitwiseOR(i,j+1) = array[i] | array[i+1]|array[i+2]|....|array[j]|array[j+1], so we can notice a fact that bitwiseOR(i,j+1) = bitwiseOR(i,j)|array[j+1]. Now we can use this relation to optimize our previous solution.
- At the jth step, we have all the bitwiseOR(i, j) in some set. Then we can find the next state of the set (for j -> j+1) by using bitwiseOR(i, j+1) = bitwiseOR(i, j) | array[j+1].
- Since there are at most 32 new values after each iteration of so at each step we have to traverse only 32 different values because any subsequent values that are different must have more 1s in it's binary representation (to a maximum of 32 ones, as the numbers are at max 32 bits long). This is due to the fact that bitwiseOR(i,j+1) >= bitwiseOR(i,j). So all the bits which are ‘set’ in bitwiseOR(i,j) will be already set in bitwiseOR(i,j+1).
- At each of the jth step we will store the bitwise OR of array[i], array[i+1],...,array[j]. And include all these sets in the answer set.
- After completing the above steps return the size of the answer set.
- Let us consider an example to better understand the algorithm, consider the array{1,6}.
- At the start initialize a vector named state( to store all the computed OR values at any step) and two pointers left and right to keep track of the previous state(jth step), here the array elements from left to right denotes the previous state. Right is generally equal to the size of the array.
- Now start traversing the array:
- As you traverse any element OR it with all the elements in the state vector(between left and right) and insert it into the state vector and also insert the element being traversed into the vector. At last change the value of the left pointer and make it equal to the previous value of right pointer and change the current value of right pointer and make it equal to current size of the vector.
- For the above example as we reach 1 our previous set only contains 0 so we will OR 1 with 0 and store the result in the vector and also we will insert 1 in the vector. Now our state vector contains {1,1}, and now we make the left equal to the previous right i.e.0 and will change the right and make it equal to 2.
- Now as we traverse 6 we OR 6 with all the values of the state vector( between left and right) and insert those into the vector in our case vector only contains two element so we will perform OR operation only with 1 and insert (1 OR 6=7) in the vector also we will insert the element being traversed(6) into the vector. So our state vector becomes {1,1,7,7,6}.
- Now we don’t have any other value to traverse.
- We will return the number of distinct values in the state vector i.e 3 in our case as the answer.
Similar problems