algoadvance

Leetcode 421. Maximum XOR of Two Numbers in an Array

Problem Statement

Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 <= i <= j < n.

Clarifying Questions

  1. Q: What should be the length of the array nums?
    • A: The input array can have any length from 1 to 2^5.
  2. Q: Can the array contain negative numbers or only non-negative integers?
    • A: The array will contain non-negative integers.
  3. Q: Is there a constraint on the values within the array?
    • A: The values will be within the range specified for integers, typically 0 to 2^31-1.

Strategy

One efficient approach to solve this problem involves using a Trie (Prefix Tree) to store binary representations of the numbers. The high-level steps are:

  1. Inserting Numbers into Trie:
    • Insert all the numbers from the array into a Trie, where each number is represented in binary form. Each node will have two children representing the binary digits (0 and 1).
  2. Calculating Maximum XOR:
    • For each number in the array, we traverse the Trie to find the number which gives the maximum XOR value with the current number. We always prefer to go in the opposite direction (i.e., if the current bit is 1, we prefer to go to 0 and vice versa) to maximize the XOR value.

Code

Here’s the Java code implementing the detailed strategy:

import java.util.*;

public class Solution {
    
    class TrieNode {
        TrieNode[] children = new TrieNode[2]; // For binary 0 and 1
    }

    public int findMaximumXOR(int[] nums) {
        TrieNode root = new TrieNode();

        // Insert each number into the Trie
        for (int num : nums) {
            TrieNode node = root;
            for (int i = 31; i >= 0; i--) {
                int bit = (num >> i) & 1;
                if (node.children[bit] == null) {
                    node.children[bit] = new TrieNode();
                }
                node = node.children[bit];
            }
        }

        int max_xor = 0;

        // Find the maximum XOR for each number
        for (int num : nums) {
            TrieNode node = root;
            int current_xor = 0;
            for (int i = 31; i >= 0; i--) {
                int bit = (num >> i) & 1;
                if (node.children[bit ^ 1] != null) { // Prefer opposite bit
                    current_xor = (current_xor << 1) | 1;
                    node = node.children[bit ^ 1];
                } else {
                    current_xor = (current_xor << 1);
                    node = node.children[bit];
                }
            }
            max_xor = Math.max(max_xor, current_xor);
        }

        return max_xor;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {3, 10, 5, 25, 2, 8};
        System.out.println(sol.findMaximumXOR(nums));  // Output: 28
    }
}

Time Complexity

This approach ensures that we can efficiently find the maximum XOR pair in an optimal time.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI