Given an Array 'A' of size N, we have to choose a 'cyclic subarray R of length N' such that the value of R[0] + R[0]^R[1] + R[0]^R[1]^R[2] + ......... + R[0]^R[1]^R[2]^.....R[N-1]^R[N]Edit: Upto R[N-1] not R[N] is maximum.
Task: You have to return/print the maximum value.
[Note: ^ represents bitwise XOR.]
Examples of Cyclic Subarray: Let's take an Array A = [2, 5, 1, 7, 9], then,
for index 0; [2, 5, 1, 7, 9] and [2, 9, 7, 1, 5] are two cyclic Subarray of size(A) = N.
Similarly, for index 1; [5, 1, 7, 9, 2] and [5, 2, 9, 7, 1] are another two cyclic Subarray of size(A) = N.
Similarly, for index 2; [1, 7, 9, 2, 5] and [1, 5, 2, 9, 7] are another two cyclic Subarray of size(A) = N.
and so on.
What should be the approach to solve this problem? I tried Applying Trie and Gaussian Elimination but I am not able to come up with a solution.
Test Case Example: Input: A = [7, 8, 5, 5, 9, 2, 2, 0, 1, 6] Output: 99
Explanation: The cyclic subarray starting at index 2(leftwards), [5, 8, 7, 6, 1, 0, 2, 2, 9, 5] will have the maximum value of 5 + 5^8 + 5^8^7 + 5^8^7^6 + 5^8^7^6^1 + 5^8^7^6^1^0 + 5^8^7^6^1^0^2 + 5^8^7^6^1^0^2^2 + 5^8^7^6^1^0^2^2^9 + 5^8^7^6^1^0^2^2^9^5 = 99
I didn't think much, but it seems to me that you can get this function from an array pretty fast. If you have two segments and for each segment you know its XOR, length and number of enabled bits in every position, you can merge them in $$$O(logA)$$$. So, what is the solution, you have to firstly write the array two times ($$$a_{i} = a_{i-n}, i > n$$$), then build segment tree and save XOR of segment, lenght of Segment and number of enabled bits in every position. Then you just have to ask $$$f(i..i+N-1)$$$ for each $$$i \in [1;n]$$$, so the answer is $$$\max_{i=1}^n{f(i..i+N-1)}$$$. Each call of function $$$get$$$ will work in $$$O(logA \cdot logN)$$$, so total complexity is $$$O(N \cdot logA \cdot logN)$$$.
PS: Maybe there exists an $$$O(NlogN)$$$ solution, if so, please reply me
You can keep the information of your seg tree for ranges [N, N+i) (or simply [0, i)) and [i, N). Building and using that to merge [i, N) + [N, N+i) ranges takes $$$O(NlogA)$$$ total.
Since I was not very much aware of Segment Tree, I am replying late because I had to learn them first. So here are couple of follow up Questions:
P.S. Please don't mind if my questions are kinda novice type.
First and thirds question seem to be quite similar.
So, lets look how we can merge two nodes. Lets look at every bit separately. If we know number of bits enabled in right side and xor of left segment, we can get number of bits in merged segment: $$$cnt = l.cnt + (l.xor ? (r.len - r.cnt) : (r.cnt)) $$$.
And about your second question, I didn't think about it right now, maybe I'll think about it later.