Arsh_a_d's blog

By Arsh_a_d, history, 2 months ago,

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