Count distinct Bitwise OR of all subarrays

Posted: 23 Nov, 2020
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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 <= 3000
1 <= ARR[i] <= 10^9

Time Limit : 1sec
Approach 1
  • 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.
Try Problem