Max Xor Subarray of size K

JavaView on GFG

Time: O(n)

Space: O(1)

Problem Overview

Find maximum XOR of any subarray of size exactly k.

Intuition

Find maximum XOR of any subarray of size exactly k. Sliding window XOR.

Algorithm

1Compute XOR of first k elements. Slide: XOR with new element and XOR out oldest. Track maximum XOR.

Common Pitfalls

• XOR of window: sliding XOR. XOR(arr[i..i+k-1]) = prefix[i+k] XOR prefix[i]. O(n).

Max Xor Subarray of size K.java

Java

// Approach: Sliding window XOR. Maintain running XOR; for a window of size k, slide and track max XOR.
// Time: O(n) Space: O(1)
class Solution {
    public int maxSubarrayXOR(int[] arr, int k) {
        int maxXOR = Integer.MIN_VALUE;

        int i = -1;
        int j = -1;
        int n = arr.length;
        int currXOR = 0;

        while (j < n) {
            if ((j - i) == k) {
                maxXOR = Math.max(maxXOR, currXOR);
                i++;
                currXOR ^= arr[i];
            }
            j++;
            if (j < n)
                currXOR ^= arr[j];
        }

        return maxXOR;
    }
}

Was this solution helpful?