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.
