Maximize Sum of running XOR

Revision en5, by Arsh_a_d, 2022-08-04 20:41:05

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: ^R[N] is not included 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

History

Revisions

Rev. Lang. By When Δ Comment
en6 Arsh_a_d 2022-08-04 20:44:38 23 (published)
en5 Arsh_a_d 2022-08-04 20:41:05 33 Tiny change: '....R[N-1]^R[N] is maximu' -> '....R[N-1] ~~^R[N]~~ is maximu' (saved to drafts)
en4 Arsh_a_d 2022-08-03 12:56:11 6 Tiny change: 'N'** such a way that the ' -> 'N'** such that the '
en3 Arsh_a_d 2022-08-03 12:54:11 475
en2 Arsh_a_d 2022-08-03 10:44:51 24
en1 Arsh_a_d 2022-08-03 10:41:01 855 Initial revision (published)