Maximum Element

Moderate
0/80
Average time to solve is 10m
profile
Contributed by
3 upvotes
Asked in company
Tata Consultancy Services (TCS)

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
6
1 3 4 2 4 5
2
1 2
Sample Output 1 :
7
2
Explanation Of Sample Input 1 :
For test case 1:

A = [1, 3, 4, 2, 4, 5]
A[3] = A[3] or A[1] = 2 | 3 = 3

A = [1, 3, 4, 3, 4, 5]
A[5] = A[5] or A[3] = 5 | 3 = 7

A = [1, 3, 4, 3, 4, 7]
Hence the maximum element we can obtain is 7.
Therefore, the answer is 7.


For test case 2:

A = [1, 2]

No operations can be performed on the array. 
Hence the maximum element we can obtain is 2.
Therefore, the answer is 2.
Sample Input 2 :
2
6
1 3 7 11 4 5
3
1 2 3
Sample Output 2 :
15
3
Hint

Handle the odd and the even indices separately.

Approaches (1)
Greedy

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).
Time Complexity

O(N), where 'N' is the length of the array ‘A’.

 

We are iterating the array ‘A’ of length ‘N’ once.

Hence, overall time complexity is O(N).

Space Complexity

 O(1).

 

We use two variables to store OR of odd and even indices, which take constant space. So the space complexity is O(1).

Code Solution
(100% EXP penalty)
Maximum Element
Full screen
Console