I am anticipating the end of this useless conversation 
I am anticipating the end of this useless conversation :P
Because from ashes of one’s end, rises another. 
1 Like
Yeah sure. Will do it by today evening.
2 Likes
Interesting solution. 
My first idea too was trie compression, but didn’t reach this solution. Thanks
2 Likes
@sdssudhu , bro can u plzz explain this
Second thing to notice here is that if we have a query string whose length > maxi, we can trim to maxi , we can take the max value from the 0 to maxBit using the Trie but the trimmed bits can also contribute to the answer if 0’s can be appended at the input string. I know i am missing something . Plzz can u correct me out.
@devil2202 Yeah the trimmed bits also contribute to the answer no doubt. But what we want is the index of the element which makes the greatest xor and not the value.
So the trimmed bits are going to remain the same for all the elements, since all bits > maxi are going to be set as 0 and 0^x=x. Hence we can ignore it
What is the time complexity of querying the compressed trie solution as explained in the answer given by @sdssudhu? Isn’t it O(Q * sqrt(length of all input strings) * log(n)) since in worst case we might visit sqrt(length of all input strings) compressed trie nodes?
The input generated by the following python code takes < 1 sec on the editorial’s solution and > 20 sec on the compressed trie solution.
print("1000 100000")
print("1"*1000)
for i in range(1, 1000):
t = "1"*i + "0" + "1"*(999-i)
print(t)
for i in range(100000):
print ("1 1000 1")
1 Like
Someone Having Step Wise explaination of this problem for beginners or any well commented code please share @vijju123 @taran_1407 , the editorial is very big and hard to understand