Maximum XOR of Two Numbers in an Array

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

Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 231.

Find the maximum result of ai XOR aj, where 0 ≤ i, j < n.

Example:

Input: [3, 10, 5, 25, 2, 8]

Output: 28

Explanation: The maximum result is 5 ^ 25 = 28.

Thoughts

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

想让一个二进制数尽量大, 那么应从高位起尽量让它们为1. 并且当高位为1时, 即使低位为0, 也比低位为1的高位为0的大. 因此我们依次从高位到低位遍历, 判断该位是否能为1, 并且利用之前高位中找出的候选者不断筛选. 比如 [110011, 110010, 010111], 当遍历到第二位时, 即使110011第二位为0, 010111第二位为1, 后者也不用再考虑了. 于是我们可以设置一个candidate表示遍历到i位时, 理想中能达到的最大的数: candidate前i - 1位为前i - 1位中能达到的数, 第i位理想情况下是1. 所以任务变为判断是否有两个数到i位时的prefix相xor能成为candidate. 这时利用xor的性质, 即当a ^ b = candidate时, 有a ^ candidate = b 且 b ^ candidate = a.

Code

class Solution {
    public int findMaximumXOR(int[] nums) {
        int max = 0, mask = 0;
        // search from left to right, find out for each bit is there 
        // two numbers that has different value
        for (int i = 31; i >= 0; i--) {
            // the mask woule be 1000..., 11000..., 111000...
            mask |= (1 << i);
            //System.out.println(Integer.toBinaryString(mask));
            Set<Integer> set = new HashSet<>();
            for (int num : nums) {
                // store prefix of all number with right i bits discarded
                set.add(num & mask);
                //System.out.println(num + "," + Integer.toBinaryString(num) + ": " + Integer.toBinaryString(mask) + "," + Integer.toBinaryString(mask & num));
            }
            // now find out if there are two prefix with different i-th bit
            // if there is, the new max should be current max with one 1 bit at i-th position, which is candidate
            // and the two prefix, say A and B, satisfies:
            // A ^ B = candidate
            // so we also have A ^ candidate = B or B ^ candidate = A
            // thus we can use this method to find out if such A and B exists in the set 
            int candidate = max | (1 << i);
            for (int prefix : set) {
                if (set.contains(candidate ^ prefix)) {
                    max = candidate;
                    break;
                }
            }
        }

        return max;
    }
}

Analysis

时间复杂度O(N).