Maximum OR sum of sub-arrays of two different arrays

Given two arrays of positive integers. Select two sub-arrays of equal size from each array and calculate maximum possible OR sum of the two sub-arrays. 

Note: Let f(x, l, r) is the OR sum of all the elements in the range [l, r] in array x. 

Examples : 

Input : A[] = {1, 2, 4, 3, 2} B[] = {2, 3, 3, 12, 1} Output : 22 Explanation: Here, one way to get maximum sum is to select sub-array [l = 2, r = 4] f(A, 2, 4) = 2|4|3 = 7 f(B, 2, 4) = 3|3|12 = 15 So, f(A, 2, 4) + f(B, 2, 4) = 7 + 15 = 22. This sum can be achieved in many other ways. Input : A[] = {1, 2, 2} B[] = {2, 1, 3} Output : 6

Observe the operation of Bitwise OR operator. If we take two integers X and Y, then (X|Y >= X). It can be proved by taking some examples. Lets derive a formula using the above equation. 
f(a, 1, i-1) | f(a, i, j) | f(a, j+1, n) >= f(a, i, j)     
and also f(a, 1, i-1) | f(a, i, j) | f(a, j+1, n) = f(a, 1, n)     
from the above two equations, f(a, 1, n) >= f(a, i, j).     
So, we get maximum sum when we take the OR of the whole array -> f(a, 1, n) + f(b, 1, n)     

Below is the implementation of above approach: 

// CPP program to find maximum OR sum #include <bits/stdc++.h> using namespace std; // function to find maximum OR sum void MaximumSum(int a[], int b[], int n) {  int sum1 = 0, sum2 = 0;    // OR sum of all the elements  // in both arrays  for (int i = 0; i < n; i++) {  sum1 |= a[i];  sum2 |= b[i];  }  cout << sum1 + sum2 << endl; } // Driver Code int main() {  int A[] = { 1, 2, 4, 3, 2 };  int B[] = { 2, 3, 3, 12, 1 };  int n = sizeof(A) / sizeof(A[0]);  MaximumSum(A, B, n);  return 0; } 

// Java program to find maximum OR sum class GFG {   // function to find maximum OR sum static void MaximumSum(int a[], int b[], int n)  {  int sum1 = 0, sum2 = 0;  // OR sum of all the elements  // in both arrays  for (int i = 0; i < n; i++) {  sum1 |= a[i];  sum2 |= b[i];  }  System.out.println(sum1 + sum2); } // Driver code public static void main(String arg[]) {  int A[] = {1, 2, 4, 3, 2};  int B[] = {2, 3, 3, 12, 1};  int n = A.length;  MaximumSum(A, B, n); } } // This code is contributed by Anant Agarwal. 

# Python 3 program to  # find maximum OR sum # function to find  # maximum OR sum def MaximumSum(a, b, n): sum1 = 0 sum2 = 0 # OR sum of all the  # elements in both arrays for i in range(0, n): sum1 |= a[i] sum2 |= b[i] print(sum1 + sum2) # Driver Code A = [ 1, 2, 4, 3, 2 ] B = [ 2, 3, 3, 12, 1 ] n = len(A) MaximumSum(A, B, n) # This code is contributed by Smitha Dinesh Semwal 

// C# program to find maximum OR sum using System; class GFG {    // function to find maximum OR sum  static void MaximumSum(int []a, int []b, int n)   {  int sum1 = 0, sum2 = 0;    // OR sum of all the elements  // in both arrays  for (int i = 0; i < n; i++)  {  sum1 |= a[i];  sum2 |= b[i];  }  Console.WriteLine(sum1 + sum2);  }    // Driver code  public static void Main()  {  int []A = {1, 2, 4, 3, 2};  int []B = {2, 3, 3, 12, 1};  int n = A.Length;  MaximumSum(A, B, n);  } } // This code is contributed by Vt_m. 

<?php // PHP program to find maximum OR sum // function to find maximum OR sum function MaximumSum($a, $b, $n) { $sum1 = 0; $sum2 = 0; // OR sum of all the elements // in both arrays for ($i = 0; $i < $n; $i++) { $sum1 |= $a[$i]; $sum2 |= $b[$i]; } echo ($sum1 + $sum2)."\n"; } // Driver Code $A = array(1, 2, 4, 3, 2 ); $B = array(2, 3, 3, 12, 1 ); $n = sizeof($A) / sizeof($A[0]); MaximumSum($A, $B, $n); // This code is contributed by mits  ?> 

<script> // JavaScript program to find maximum OR sum // function to find maximum OR sum function MaximumSum(a, b, n)  {  let sum1 = 0, sum2 = 0;    // OR sum of all the elements  // in both arrays  for (let i = 0; i < n; i++) {  sum1 |= a[i];  sum2 |= b[i];  }  document.write(sum1 + sum2); } // Driver code    let A = [1, 2, 4, 3, 2];  let B = [2, 3, 3, 12, 1];  let n = A.length;  MaximumSum(A, B, n);   </script> 

22 

Time Complexity: O(n)
Auxiliary Space: O(1)