New update is available. Click here to update.

Count distinct Bitwise OR of all subarrays

Posted: 23 Nov, 2020
Difficulty: Easy


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


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. 
You do not need to print anything, it has already been taken care of. Just implement the given function.
1 <= T <= 100
1 <= N <= 3000
1 <= ARR[i] <= 10^9

Time Limit : 1sec