BINSTR - EDITORIAL

@taran_1407 Added the explanation as a separate answer here.

1 Like

Interesting solution. :slight_smile:

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")

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