Count distinct Bitwise OR of all subarrays

Easy
0/40
Average time to solve is 10m
24 upvotes
Asked in companies
OYOOlaSamsung R&D Institute

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
1
3
1 2 3
Sample Output 1:
3
Explanation for sample input 1:
The possible subarrays of {1,2,3} are {1},{2},{3},{1,2},{1,2,3},{2,3}. And bitwise ORs of all the elements for all the subarrays will be 1,2,3,3,3,3 respectively. So, the count of distinct OR will be 3.
Sample Input 2:
1
2
1 5
Sample Output 2:
2
Explanation for sample input 2:
The possible subarrays of {1,5} are {1},{5},{1,5}. And bitwise ORs of the elements for all the subarrays will be 1,5,5 respectively. So, the count of distinct OR will be 2.
Hint

Traverse over all possible subarrays and calculate their bitwise OR

Approaches (2)
Brute Force
  • 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.
Time Complexity

O(N ^ 2), where N is the size of the array.

 

We are traversing the array ARR in nested for loops to generate all the respective subsets and then storing the unique values obtained after performing bitwise OR among them. Therefore the complexity grows of the order O(N ^ 2).

Space Complexity

O(N * log(W)), where N is the size of the array and W is the largest integer present in the input array.

 

We are using a vector of size N with the largest integer W present. Each integer value would require log(W) bits binary representation storage as a result of which the space complexity here is O(N * log(W)).

Code Solution
(100% EXP penalty)
Count distinct Bitwise OR of all subarrays
Full screen
Console