CDSW151 - Editorial

PROBLEM LINK:

Practice

Contest

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.

Nice One…:slight_smile: