Last Updated: 21 Jul, 2022

Maximum Element

Moderate

Problem statement

There is an array ‘A’ of length ‘N’. You can perform the following operation on the array, select ‘i’, ‘1< i <= N - 1’ and replace ‘A[i]’ with ‘A[i] | A[i - 2]’, where ‘|’ represents bitwise OR operation.

Your task is to find the maximum element ‘X’ you can obtain by operating zero or more times.

Example:

‘A’ = [1, 3, 2, 5]

A[3] = A[3] or A[1] = 3 | 5 = 7    
‘A’ = [1, 3, 2, 7]
Hence the maximum element we can obtain is 7.
Therefore, the answer is 7.

Input Format

First-line contains 'T,' denoting the number of Test cases.

For each Test case:

The first line contains an integer ‘N’ denoting the number of students.
The second line contains ‘N’ elements of array ‘A’.

Output format :

Return the maximum element ‘X’ you can obtain by operating zero or more times.

Note:-

You don't need to print anything. Just implement the given function.

Constraints :

1 <= 'T' <= 10
1 <= 'N' <= 10^5
1 <= 'A[i]' <= 2^30


Time Limit: 1 sec

Solve now

Approaches

01 Approach

Approach:-

We can OR all the elements with the same parity with each other after some operations. ( A[3]=(A[3] | A[1]) , A[5] = (A[5] | A[3]) = (A[5] | A[3] | A[1])).
Hence, finding OR of all elements present at the same parity will lead to the solution.
Find OR of all the elements at even indices.
Find OR of all the elements at odd indices.
The maximum among them is the answer.

Algorithm:-

Initialize two variables ‘odd’ and ‘even’ to zero.
‘i’ = 0.
while ‘i’ < n:
- ‘odd’ |= ‘A[i]’.
- ‘i’ += 2.
‘i’ = 1
while ‘i’ < n:
- ‘even’ |= ‘A[i]’.
- ‘i’ += 2.
Return max (odd, even).

Solve now