XOR Problems using Trie
A Trie because of its re Trie Val property can be used to solve many problems that require to find the maximum XOR values or problems involving XOR. In this post, we will discuss similar problems where Trie can be used to solve them. Reference Links: Tutorials on Trie Lets Jump to some questions : Question 1: MAX_XOR Given an array of integers , we have to find two elements whose XOR is maximum. Explanation: We First insert our numbers as bits in the Trie as we go. Now for finding the max XOR we start from the MSB and check along. Let's say our number Y is b1,b2...bn, where b1,b2.. are binary bits. We start from b1. Now for the XOR to be maximum, we'll try to make most significant bit 1 after taking XOR. So, if b1 is 0, we'll need a 1 and vice versa. In the trie, we go to the required bit side. If favorable option is not there, we'll go other side. Doing this all over for i=1 to n, we'll get the maximum XOR possible. ...