Maximise the OR Sum
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.

Input Format:

The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow. The first line of each test case contains an integer ‘N’ denoting the number of elements in the array. The second line contains ‘N’ space-separated integers denoting the elements of the first array. The third line contains ‘N’ space-separated integers denoting the elements of the second array.

Output Format:

For each test case, print an integer denoting the maximum OR sum. Output for each test case will be printed in a separate line.

Note:

You are not required to print anything; it has already been taken care of. Just implement the function.

Constraints:

1

Question

Maximise the OR Sum

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.

Input Format:

The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow.

The first line of each test case contains an integer ‘N’ denoting the number of elements in the array.

The second line contains ‘N’ space-separated integers denoting the elements of the first array.

The third line contains ‘N’ space-separated integers denoting the elements of the second array.

Output Format:

For each test case, print an integer denoting the maximum OR sum.

Output for each test case will be printed in a separate line.

Note:

You are not required to print anything; it has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 10
1 <= N <= 10^5
1 <= arr1[i], arr2[i] <= 10^5

Time Limit: 1 sec.

Accepted Answer

Using Logical OR Property

Find the OR sum of both arrays and add them as the logical OR of two Numbers is always greater than or equal to the two numbers.

Algorithm :

Declare two variables ‘SUM1’ and ‘SUM2’ of type integer and initialize them with 0.
Iterate from 0 to ‘N’ - 1 on both arrays i.e. ‘ARR1’ and ‘ARR2’. (say iterator be i).
1. Update ‘SUM1’ as ‘SUM1’ = ‘SUM1’ | ‘ARR1[i]’.
2. Update ‘SUM2’ as ‘SUM2’ = ‘SUM2’ | ‘ARR2[i]’.
Return ‘SUM1’ + ‘SUM2’.

Space Complexity: O(1)Explanation:

O(1).

Constant extra space is used.

Time Complexity: O(n)Explanation:

O(N), where N is the number of elements in the array.

Since we are traversing on both the array once, the overall time complexity will be O(N).

Java (SE 1.8)

/*
    Time Complexity :- O(n)
    Space Complexity :- O(1)

    Where 'n' is number of elements in the array.

*/

public class Solution {
    public static int maximumOrSum(int arr1[], int arr2[], int n) {
        
        // This will store the OR of all elements of first array.
        int sum1 = 0 ;
        // This will store the OR of all elements of first array.
        int sum2 = 0;
        
        // This loop is used to calculate OR of all  elements of both arrays.
        for(int i = 0; i < n; i++) {
            sum1 |= arr1[i];
            sum2 |= arr2[i];
        }
        
        // The maxSum is will the sum of OR of both the arrays.
        int maxSum = sum1 + sum2;
        
        return maxSum;
    }
}

Python (3.5)

'''
    Time Complexity :- O(n)
    Space Complexity :- O(1)
    
    Where 'n' is number of elements in the array.

'''

def maximumOrSum(arr1, arr2, n):
    
    # This will store the OR of all elements of first array.
    sum1= 0
    
    # This will store the OR of all elements of first array.
    sum2 = 0
    
    # This loop is used to calculate OR of all  elements of both arrays.
    for i in range(n):
        
        sum1 |= arr1[i]
        sum2 |= arr2[i]
        
    # The maxSum is will the sum of OR of both the arrays.
    maxSum = sum1 + sum2
    
    return maxSum

C++ (g++ 5.4)

/*

	Time Complexity :- O(n)

	Space Complexity :- O(1)



	Where 'n' is number of elements in the array.



*/



int maximumOrSum(vector arr1,vector arr2, int n){



        // This will store the OR of all elements of first array.

		int sum1 = 0 ;



		// This will store the OR of all elements of first array.

		int sum2 = 0;

		

		// This loop is used to calculate OR of all  elements of both arrays.

		for(int i = 0; i < n; i++) {

			sum1 |= arr1[i];

			sum2 |= arr2[i];

		}

		

		// The maxSum is will the sum of OR of both the arrays.

		int maxSum = sum1 + sum2;

		

		return maxSum;



}