Maximum XOR of Two Numbers in an Array 🎯

Welcome to this comprehensive guide on finding the Maximum XOR of Two Numbers in an Array! This lesson is designed to help both beginners and intermediates understand and solve this problem with ease. Let's dive right in!

Understanding the Problem 📝

Given an array of non-negative integers, find the maximum result of XOR between any two numbers in the array.

Breaking it Down 💡

XOR (Exclusive OR) is a binary operation that gives 1 if the two bits are different and 0 if they are the same.
In our case, we are dealing with non-negative integers, so we can break them down into their binary representations and perform XOR operation.

Pseudo Code 💡

maxXor = -1
for each number in the array:
    for each other number in the array (excluding the current number):
        xor = current number XOR other number
        if xor > maxXor:
            maxXor = xor

Implementation 💡

Now, let's see how we can implement this in code. We'll use Python for this example, but the concept applies to other programming languages as well.

python

def findMaxXor(arr):
    maxXor = -1
    for i in arr:
        for j in arr:
            if i != j:
                xor = i ^ j
                if xor > maxXor:
                    maxXor = xor
    return maxXor

arr = [1, 3, 5, 7, 9]
print(findMaxXor(arr))  # Output: 8

In the above code, we define a function findMaxXor(arr) that takes an array as an argument and returns the maximum XOR of two numbers in the array. We then create an example array and call the function to find the maximum XOR.

Advanced Techniques 💡

For large arrays, we can use a more efficient approach by sorting the array first and then finding the maximum XOR. This technique can help us reduce the time complexity from O(n^2) to O(n log n).

python

def findMaxXor(arr):
    arr.sort()
    maxXor = 0
    for i in range(len(arr)):
        maxXor = max(maxXor, arr[i] ^ arr[-1 - i])
    return maxXor

In the above code, we first sort the array, and then we perform XOR between each number and the last number. This way, we can find the maximum XOR in linear time.

Quiz 🎯

That's all for this comprehensive guide on finding the Maximum XOR of Two Numbers in an Array! Practice, practice, and more practice to master this concept and solve real-world problems with ease. Happy coding! 🚀💻🙌