1391. Find Subarray with Maximum XOR

HardBit ManipulationXOR TriePrefix XORSubarray

Given an array of non-negative integers, find a non-empty contiguous subarray whose XOR is maximum and return its boundaries as [start, end] using 0-indexed inclusive positions. If several subarrays achieve the maximum XOR, return the one with the smallest start index, breaking further ties by the smallest end index.

Input: A JSON object {"arr": [<non-negative integers>]}.

Output: Return [start, end] of a maximum-XOR subarray under the stated tie-breaking.

Examples

Example 1
Input: {"arr":[1,2,3,4]}
Output: [2,3]
Explanation: The maximum XOR 7 comes from indices 2..3.
Example 2
Input: {"arr":[4,1,1]}
Output: [0,1]
Explanation: The single element 4 is the maximum -> [0,0].

Constraints

Asked by

AmazonGoogleMicrosoftMetaAdobe
Solve this problem in the editor →