This problem came in their coding challenge. Can anyone solve it ?
Problem Statement
You are given 2 integer array, A and B, of length n. Your task is to maximize xor-sum of the arrays.
Xor-sum of 2 arrays is defined as the S = (A[0] ^ B[0]) + (A[1] ^ B[1]) + ..... + (A[n — 1] ^ B[n — 1]). Expression (x ^ y) is means applying Bitwise Excluding Or operation on x and y.
There is a twist in the problem. You are allowed to reverse at most one subarray of array A. Find maximum possible Xor-sum.
Constraints
1 <= n <= 5000
1 <= Ai <= 10^5
1 <= Bi <= 10^5
Test Case
Q) A = {1, 2} , B = {1, 2}
Ans) 6 (Reverse whole of subarray A and then find Xor-sum)
Similar problem Maximize the sum of the product of two arrays with xor instead of the product and rest is same approach.
Thanks
I think this solution fits with the constraints.
First of all you create an array ps where ps[i] = ps[i-1]+(a[i]^b[i]), ps[0] = a[0]^b[0].
Since reversing the segment i, i+1, ..., j-1, j, is the same as reversing i+1, i+2,..., j-2, j-1 and then reversing i and j, you can use this to calculate all the options of reversing a segment centered on position x on O(n). You just have to add the xor of the extremes inversed in each operation. And then use the array ps to add the part that have not been reversed.
After that you should iterate again over a and do almost the same but instead of checking segment of odd length, check the ones with even length.
The total complexity of this is O(n^2)
for subarray $$$j..i$$$ of length len
let $$$dp[i][len]$$$ denotes the $$$xor \ sum$$$ of $$$A[i..j]$$$ and $$$B[j..i]$$$
moving from $$$dp[i][len]$$$ to $$$dp[i + 1][len + 1]$$$ requires $$$O(n)$$$ time but
we can move from $$$dp[i][len]$$$ to $$$dp[i + 1][len + 2]$$$ in $$$O(1)$$$ time
so we can calculate dp values for odd and even length subarrays separately in $$$O(n^2)$$$
now you can easily choose the subarray which maximizes the ans