You are given an array, find the minimum k, such that the count of number of subarrays whose xor is atmost k, is atleast x.
1<=N<=1e5
1<=X<=N*(N+1)/2
Sample Input
4 7
1 2 3 4
Output
4
Subarrays are
{1} {1,2} {1,2,3} {2,3} {2} {3} {4} {1,2,3,4} (count of number of subarrays with xor atmost 4 is 8)
Note: XOR of a subarray is the xor of all the elements in the subarray
I tried binary searching on k, and each time found the count of subarrays with xor less or
equal to k, but that involved trie and heavy implementation, any other simpler approach?
665E. Beautiful Subarrays problem is exact oppsite of the one you asked. This problem asks for atleast k and the one you asked is for atmost k so basically you can apply same logic but for atmost k number of such subarrays, it will be total subarrays i.e.
n * (n + 1) / 2 - number of subarrays with xor atleast k+1.