Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Maximise the OR Sum

Easy
0/40
Average time to solve is 20m
profile
Contributed by
5 upvotes
Asked in company
Elgin Industries

Problem statement

You are given two arrays of the positive integers. You are required to select two sub-arrays of equal length, one from each array, such that the sum of the OR of two sub-arrays is maximum. Your task is to return the maximum sum possible.

An array ‘C’ is a subarray of array ‘D’ if ‘C’ can be obtained from ‘D’ by deletion of several elements from the beginning and several elements from the end.

Example : let ‘arr’ = [1,0,0] then the possible subarrays of ‘arr’ will be- {1}, {0},{0},{1,0},{0,0},{1,0,0}.

For Example:
Let the first array be : ‘arr1’ = {1,5,8,4} and the second array be ‘arr2’ = {3,7,16,1}

For this, the maximum sum takes the sub-array {5,8} from the first ‘arr1’ and {7,16} from arrays, two, the OR sum will be 13 + 23 = 26, which is maximum.
Detailed explanation ( Input/output format, Notes, Images )
Constraints:
1 <= T <= 10
1 <= N <= 10^5
1 <= arr1[i], arr2[i] <= 10^5

Time Limit: 1 sec.
Sample Input 1:
2
4
1 5 8 4
3 7 16  1 
5
1 3 4 2 2
1 3 12 3 1
Sample Output 1:
36
22
Explanation For Sample Output 1:
For test case one:-
Select subarray {3,4,2} and {3,12,3}, the max OR sum will be 22.

For test case two:-
Select subarray {5,8} and {7,16}, the max OR sum will be 36.
Sample Input 2:
2
5
1 2 3 4 5
6 7 8 9 10
5
1 3 5 7 9
2 4 6 8 10
Sample Output 2:
22
29
Full screen
Console