### PROBLEM LINK:

**Author:** Pranjul Dubey

**Editorialist:** Swapnil Saxena

### DIFFICULTY:

EASY

### PREREQUISITES:

Preprocessing

### EXPLANATION:

The question is to find the starting position of window of length k such that the xor of all the elements in that window is minimum. If multiple such windows exists we have to report the starting position with max_index.

A naive solution would involve considering all the windows of lengths k. (Note: The no. of such windows is (n-k+1)). For every window, just iterate through all the elements and compare it with the current minimum. If is smaller or equal update the minimum position.

However this is a O((n-k+1)*k) solution. To fasten it up one can use preprocessing. Maintain an array prefix_xor where prefix_xor(i) = a1 ^ a2 ^ … ^ ai. Using this ‘prefix_xor’ array, finding the xor of a range becomes O(1) as XOR-SUM of a range [i, j] is just prefix_xor[i-1] ^ prefix_xor[j] for i < j.

This will reduce the complexity to O(n + (n – k + 1))

### AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution can be found here.