Max Xor Subarray of size K

JavaView on GFG

Time: O(n)

Space: O(1)

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?