Maximum Subarray VI

Question

Given an array of integers. find the maximum XOR subarray value in given array.
What's the XOR: https://en.wikipedia.org/wiki/Exclusive_or

Notice

Expected time complexity O(n).

Answer

https://threads-iiith.quora.com/Tutorial-on-Trie-and-example-problems
Let's say F(L,R) is XOR of subarray from L to R.
Here we use the property that F(L,R)=F(1,R) XOR F(1,L-1). How?
Let's say our subarray with maximum XOR ended at position i. Now, we need to maximise F(L,i) ie. F(1,i) XOR F(1,L-1) where L<=i. Suppose, we inserted F(1,L-1) in our trie for all L<=i, then it's just problem1.

class Solution {
public:
    /*
     * @param : the array
     * @return: the max xor sum of the subarray in a given array
     */    
    int maxXorSubarray(vector<int> &nums) {
        // write code here
        int ans = INT_MIN;
        int pre = 0;
        Trie trie;
        for (auto n : nums) {
            pre = pre ^ n;
            trie.insert(pre);
            ans = max(ans, trie.query(pre));
        }
        return ans;
    }
private:    
    class Trie {
    public:
        Trie() {
            root = new TrieNode(0);
            INTBITS = sizeof(int) * 8;
        }
        void insert(int x) {
            TrieNode* iter = root;
            for (int i = INTBITS - 1; i >= 0; i--) {
                bool v = x & (1 << i);
                if (iter->arr[v] == 0)
                    iter->arr[v] = new TrieNode(0);
                iter = iter->arr[v];
            }
            iter->val = x;
        }
        int query(int x) {
            TrieNode* iter = root;
            for (int i = INTBITS - 1; i >= 0; i--) {
                bool v = x & (1 << i);
                if (iter->arr[1-v] != 0)
                    iter = iter->arr[1-v];
                else if (iter->arr[v] != 0)
                    iter = iter->arr[v];
            }
            return x ^ iter->val;
        }
    private:
        class TrieNode {
        public:
            int val;
            TrieNode *arr[2];
            TrieNode(int v)
                : val(v) {
                arr[0] = arr[1] = 0;
            }
        };
        TrieNode* root;
        int INTBITS;
    };    
};

❤️ Support This Blog

---

If this post helped you, you can support my writing with a small donation. Thank you for reading.

---

Coffee ☕ Thanks 🙏 Extra Support ❤️