0421. Maximum XOR of Two Numbers in an Array

https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array

Description

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

Example 1:

**Input:** nums = [3,10,5,25,2,8]
**Output:** 28
**Explanation:** The maximum result is 5 XOR 25 = 28.

Example 2:

**Input:** nums = [0]
**Output:** 0

Example 3:

**Input:** nums = [2,4]
**Output:** 6

Example 4:

**Input:** nums = [8,10,2]
**Output:** 10

Example 5:

**Input:** nums = [14,70,53,83,49,91,36,80,92,51,66,70]
**Output:** 127

Constraints:

• 1 <= nums.length <= 2 * 105

• 0 <= nums[i] <= 231 - 1

ac1: Trie

class Solution {
    public int findMaximumXOR(int[] nums) {
        TrieNode root = new TrieNode();
        // build trie
        for (int n : nums) {
            build(root, n);
        }

        int max = 0;
        for (int n : nums) {
            TrieNode r = root;
            int tmp = 0;
            for (int i = 31; i >=0; i--) {
                int currBit = (n >>> i) & 1;
                // so the currbit is 0 or 1, I want to see whether I can XOR one val in trie to get 1 in this bit
                // KEY: currBit ^ x = 1 -> currBit ^ 1 = x;
                TrieNode next = r.next[currBit ^ 1];
                if (next != null) { // can XOR to 1, add to value
                    tmp += 1 << i;
                    r = next;
                } else {
                    r = r.next[currBit]; // can't XOR to 1. if currBit is 1, then val in trie is 1, if currBit is 0, it is 0.
                }
            }
            max = Math.max(max, tmp);
        }

        return max;
    }
    private void build(TrieNode root, int n) {
        for (int i = 31; i >=0; i--) {
            int pos = (n >>> i) & 1; // val at digit i.
            if (root.next[pos] == null) root.next[pos] = new TrieNode();
            root = root.next[pos];
        }
    }
}

class TrieNode {
    TrieNode[] next;
    public TrieNode() {
        next = new TrieNode[2]; // 0 or 1
    }
}

/*
from left to right, try every bit, see if can XOR to 1
*/

ac2: Greedy?

Too complicated for an interview.

https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/discuss/91049/Java-O(n)-solution-using-bit-manipulation-and-HashMap/95535

public int findMaximumXOR(int[] nums) {
    int maxResult = 0; 
    int mask = 0;
    /*The maxResult is a record of the largest XOR we got so far. if it's 11100 at i = 2, it means 
    before we reach the last two bits, 11100 is the biggest XOR we have, and we're going to explore
    whether we can get another two '1's and put them into maxResult

    This is a greedy part, since we're looking for the largest XOR, we start 
    from the very begining, aka, the 31st postition of bits. */
    for (int i = 31; i >= 0; i--) {

        //The mask will grow like  100..000 , 110..000, 111..000,  then 1111...111
        //for each iteration, we only care about the left parts
        mask = mask | (1 << i);

        Set<Integer> set = new HashSet<>();
        for (int num : nums) {

            /* we only care about the left parts, for example, if i = 2, then we have
            {1100, 1000, 0100, 0000} from {1110, 1011, 0111, 0010}*/
            int leftPartOfNum = num & mask;
            set.add(leftPartOfNum);
        }

        // if i = 1 and before this iteration, the maxResult we have now is 1100, 
        // my wish is the maxResult will grow to 1110, so I will try to find a candidate
        // which can give me the greedyTry;
        int greedyTry = maxResult | (1 << i);

        for (int leftPartOfNum : set) {
            //This is the most tricky part, coming from a fact that if a ^ b = c, then a ^ c = b;
            // now we have the 'c', which is greedyTry, and we have the 'a', which is leftPartOfNum
            // If we hope the formula a ^ b = c to be valid, then we need the b, 
            // and to get b, we need a ^ c, if a ^ c exisited in our set, then we're good to go
            int anotherNum = leftPartOfNum ^ greedyTry;
            if (set.contains(anotherNum)) {
                maxResult= greedyTry;
                break;
            }
        }

        // If unfortunately, we didn't get the greedyTry, we still have our max, 
        // So after this iteration, the max will stay at 1100.
    }

    return maxResult;
}