All Tracks Data Structures Advanced Data Structures Trie (Keyword Tree) Problem

Substring Xor
Tag(s):

Binary search algorithm, Data Structures, Medium, Trie

Problem
Editorial
Analytics

Given a length-n array a and a number k, there are \(\frac{n \times (n + 1)}{2}\) subarrays in total. For each subarray, we can compute the xor sum of its elements.

In this problem, we will sort all these xor-sums in non-increasing order. And we want to find the \(k^{th}\) element.

\(\textbf{Input}\)

The first line contains two numbers n (\(1 \le n \le 100 000\)) and k (\(1 \le k \le \frac{n \times(n + 1)}{2}\)).

The second line contains n numbers - \(a_1, a_2, a_3, \dots , a_n\) (\(0 \le a_i < 2^{20}\)).

\(\textbf{Output}\)

Output the \(k^{th}\) element in the non-increasing order.

SAMPLE INPUT
5 10
1 4 3 12 8
SAMPLE OUTPUT
4
Explanation

All the xors of subarrays are \((15,12,11,10,8,7,7,6,5,4,4,3,3,2,1)\), the \(10^{th}\) is 4.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

November Circuits '17

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?