OrOasis

1.8

5 votes
Bit Manipulation, Algorithms, Greedy Algorithms, Basics of Greedy Algorithms
Problem

Consider an array A with N elements. The task is to identify the shortest possible contiguous subarray where the Bitwise OR of the elements within the subarray equals the Bitwise OR of the elements outside the subarray. Additionally, determine the count of all such minimal-length subarrays that meet this condition.

Note:

  • The subarray of A is a contiguous part of the array A, i. e. the array Ai,Ai+1,....,Aj for some 1ijN.
  • If in the given array there exists no such subarray for which the Bitwise OR of the elements within the subarray equals the Bitwise OR of the elements, print a single integer 1.

Input format

  • The first line contains a single integer T, which denotes the number of test cases.
  • For each test case:
    • The first line contains N denoting the size of array A.
    • The second line contains N space-separated integers, denoting the elements of A.

Output format

For each test case, If the answer exists, print 2 integers, where the first one is the shortest possible contiguous subarray where the Bitwise OR of the elements within the subarray equals the Bitwise OR of the elements outside the subarray, & the second one is the count of all such minimal-length subarrays, in a new line, Otherwise If in the given array there exists no such subarray for which the Bitwise OR of the elements within the subarray equals the Bitwise OR of the elements, print a single integer -1, in a new line.

Constraints

1T1052N1060<A[i]109  i[1,N]The sum of all values of N over all test cases doesn't exceed 106

Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

The first line denotes T = 1.

For test case 1, we are given: 

  • N = 6
  • A = [1, 2, 1, 2, 2, 1]

In the given array, there are the following 4 smallest-sized subarrays with their Bitwise OR of the elements within the subarray equaling the Bitwise OR of the elements outside the subarray.

  • from position 1 to position 2  [1, 2]
  • from position 2 to position 3  [2, 1]
  • from position to position  [1, 2]
  • from position 5 to position 6  [2, 1]

Thus, the answer is 2 4.

For test case 2, we are given:

  • N = 3
  • A = [1, 2, 4]

In the given array, there exists no such subarray for which the Bitwise OR of the elements within the subarray equals the Bitwise OR of the elements outside the subarray.

Thus, the answer is -1.

Editor Image

?