Maximum Xor Of Two Numbers In An Array

                                            
class TrieNode {
public:
    TrieNode* next[2];
    
    TrieNode() {
        next[0] = nullptr;
        next[1] = nullptr;
    }
};

class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        TrieNode* root = new TrieNode();
        int maxXor = 0;
        
        for (int i = 0; i < nums.size(); i++) {
            TrieNode* curr = root;
            TrieNode* complement = root;
            int value = nums[i];
            int currentXor = 0;
            
            for (int j = 31; j >= 0; j--) {
                int bit = (value >> j) & 1;
                
                if (curr->next[bit] == nullptr) {
                    curr->next[bit] = new TrieNode();
                }
                curr = curr->next[bit];
                
                int complementBit = 1 - bit;
                if (complement->next[complementBit] != nullptr) {
                    currentXor += (1 << j);
                    complement = complement->next[complementBit];
                } else {
                    complement = complement->next[bit];
                }
            }
            
            maxXor = max(maxXor, currentXor);
        }
        
        return maxXor;
    }
};

                                            
class Solution {
    public int findMaximumXOR(int[] nums) {
        int max = 0, mask = 0;
        for (int i = 31; i >= 0; i--) {
            mask |= (1 << i);
            Set<Integer> set = new HashSet<>();
            for (int num : nums) {
                set.add(num & mask);
            }
            int candidate = max | (1 << i);
            for (int prefix : set) {
                if (set.contains(prefix ^ candidate)) {
                    max = candidate;
                    break;
                }
            }
        }
        return max;
    }
}

                                            
class Solution(object):
    def findMaximumXOR(self, nums):
        ans = 0
        mask = 0
        for i in range(31, -1, -1):
            mask |= (1 << i)
            seen = set()
            for num in nums:
                seen.add(num & mask)
            temp = ans | (1 << i)
            for prefix in seen:
                if temp ^ prefix in seen:
                    ans = temp
                    break
        return ans

                                            
public class Solution {
    public int FindMaximumXOR(int[] nums) {
        int max = 0, mask = 0;
        for (int i = 31; i >= 0; i--) {
            mask |= 1 << i;
            HashSet<int> set = new HashSet<int>();
            foreach (int num in nums) {
                set.Add(num & mask);
            }
            int tmp = max | (1 << i);
            foreach (int prefix in set) {
                if (set.Contains(tmp ^ prefix)) {
                    max = tmp;
                    break;
                }
            }
        }
        return max;
    }
}

                                            
function findMaximumXOR(nums: number[]): number {
    let maxResult = 0;
    let mask = 0;
    
    for (let i = 31; i >= 0; i--) {
        mask |= (1 << i);
        const set = new Set<number>();
        for (const num of nums) {
            set.add(num & mask);
        }
        const tempResult = maxResult | (1 << i);
        for (const prefix of set) {
            if (set.has(prefix ^ tempResult)) {
                maxResult = tempResult;
                break;
            }
        }
    }
    
    return maxResult;
};

                                            
class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function findMaximumXOR($nums) {
        $maxXOR = 0;
        $mask = 0;
        for ($i = 31; $i >= 0; $i--) {
            $mask |= (1 << $i);
            $set = [];
            foreach ($nums as $num) {
                $set[] = $num & $mask;
            }
            $tmp = $maxXOR | (1 << $i);
            foreach ($set as $prefix) {
                if (in_array($prefix ^ $tmp, $set)) {
                    $maxXOR = $tmp;
                    break;
                }
            }
        }
        return $maxXOR;
    }
}

                                            
class Solution {
    fun findMaximumXOR(nums: IntArray): Int {
        var maxXor = 0
        var mask = 0
        for (i in 31 downTo 0) {
            mask = mask or (1 shl i)
            val set = HashSet<Int>()
            for (num in nums) {
                set.add(num and mask)
            }
            val temp = maxXor or (1 shl i)
            for (prefix in set) {
                if (set.contains(temp xor prefix)) {
                    maxXor = temp
                    break
                }
            }
        }
        return maxXor
    }
}

                                            
class Solution {
  int findMaximumXOR(List<int> nums) {
    int result = 0;
    int mask = 0;
    
    for (int i = 31; i >= 0; i--) {
      mask |= (1 << i);
      Set<int> prefixes = Set();
      for (int num in nums) {
        prefixes.add(num & mask);
      }
      int temp = result | (1 << i);
      for (int prefix in prefixes) {
        if (prefixes.contains(temp ^ prefix)) {
          result = temp;
          break;
        }
      }
    }
    
    return result;
  }
}

                                            
# @param {Integer[]} nums
# @return {Integer}
def find_maximum_xor(nums)
    result = 0
    mask = 0
    (31).downto(0) do |bit|
        mask |= (1 << bit)
        prefixes = Set.new
        nums.each { |num| prefixes.add(num & mask) }
        
        temp = result | (1 << bit)
        prefixes.each do |prefix|
            if prefixes.include?(temp ^ prefix)
                result = temp
                break
            end
        end
    end
    
    result
end

                                            
object Solution {
    def findMaximumXOR(nums: Array[Int]): Int = {
        var result = 0
        var mask = 0
        for (i <- 31 to 0 by -1) {
            mask = mask | (1 << i)
            val set = nums.map(_ & mask).toSet
            val next = result | (1 << i)
            for (prefix <- set) {
                if (set.contains(prefix ^ next)) {
                    result = next
                }
            }
        }
        result
    }
}

                                            
impl Solution {
    pub fn find_maximum_xor(nums: Vec<i32>) -> i32 {
        let mut max_xor = 0;
        
        for i in 0..nums.len() {
            for j in i..nums.len() {
                max_xor = max_xor.max(nums[i] ^ nums[j]);
            }
        }
        
        max_xor
    }
}

To solve this coding challenge, we need to identify the maximum result of XORing any two numbers in a given array. XOR (exclusive OR) is a bitwise operation that returns 1 for each bit position where the corresponding bits of the operands differ and 0 where they are the same. Here's a detailed explanation and pseudocode to solve the problem:

# Explanation

Understanding XOR Basis : XOR combines bits in a way such that for each bit pair, it results in 1 if the bits differ and 0 if they are the same. For instance, for the numbers 5 (in binary '0101') and 25 (in binary '11001'), XOR results in '011100', equal to 28 in decimal. Thus, 5 XOR 25 = 28.
Iterating Bit Positions : We aim to maximize the XOR result bit by bit, starting from the most significant bit (MSB) and working our way to the least significant bit (LSB). The idea is to use the properties of the numbers' binary representations to build candidates of potential maximum results.
Using a Mask : We utilize a mask to isolate current bits of interest. For each bit, we keep track of seen prefixes of the given numbers with that mask applied. This helps us in identifying potential pairs that could maximize the XOR value.
Checking Candidates : For each bit position, after updating our mask, we check if flipping the current bit (from 0 to 1 or vice versa) of a candidate maximum result leads to already seen prefixes. This helps in deciding if we can set the current bit in our candidate maximum result to 1.

Here's a step-by-step explanation in pseudocode:

# Detailed Steps in Pseudocode

Initialize
max_result

to store the maximum XOR found, and
mask

to construct prefixes.
Loop over bit positions from the MSB to the LSB.
Inside this loop, adjust the
mask

to consider the current bit and all more significant bits.
Use the
mask

to generate prefixes.
Assume the current bit in the final result can be 1 (set this in a candidate).
Check if existing prefixes can create this candidate value using XOR.
If they can, update the
max_result

to reflect this. Continue to the next bit.

# Pseudocode with Comments:

                                            
# Initialize variables for storing the maximum XOR result and the mask
max_result = 0
mask = 0

# Iterate over bit positions from most significant bit (31) to least significant bit (0)
for bit_position from 31 down to 0:
    # Update the mask to consider the current bit and all more significant bits
    mask = mask | (1 << bit_position)
    
    # Use a set to track seen prefixes of numbers with the applied mask
    seen_prefixes = set()
    for number in numbers:
        # Extract prefix with the current mask and add to the set of seen prefixes
        seen_prefix = number & mask
        seen_prefixes.add(seen_prefix)
    
    # Assume the current bit of the result can be set to 1 (this is the candidate)
    candidate_max_result = max_result | (1 << bit_position)
    
    # Check if the candidate can be achieved with any of the seen prefixes
    for prefix in seen_prefixes:
        # If the XOR of the candidate with the current prefix is also a seen prefix
        if (candidate_max_result ^ prefix) in seen_prefixes:
            # Update max_result to the candidate value as it is achievable
            max_result = candidate_max_result
            break

# Return the maximum XOR result found
return max_result

In summary, by constructing and using masks to isolate current bit positions, and using sets to track prefixes, we can iteratively build towards the maximum possible XOR of any two numbers from the input array. This approach ensures efficient calculation by using bitwise operations and set manipulations, allowing us to solve the problem within reasonable time limits even for large inputs.