Java O(n) solution using bit manipulation and HashMap


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

  • 6
    C

    @tangx668 Could you explain your codes? Thanks!


  • 101
    N

    This algorithm's idea is:
    to iteratively determine what would be each bit of the final result from left to right. And it narrows down the candidate group iteration by iteration. e.g. assume input are a,b,c,d,...z, 26 integers in total. In first iteration, if you found that a, d, e, h, u differs on the MSB(most significant bit), so you are sure your final result's MSB is set. Now in second iteration, you try to see if among a, d, e, h, u there are at least two numbers make the 2nd MSB differs, if yes, then definitely, the 2nd MSB will be set in the final result. And maybe at this point the candidate group shinks from a,d,e,h,u to a, e, h. Implicitly, every iteration, you are narrowing down the candidate group, but you don't need to track how the group is shrinking, you only cares about the final result.


  • 0
    T

    Great work!!


  • -3
    D

    This isn't O(n) though. It's more like O(n log W) because we have W bits worth of word width (W being the max number possible).


  • 6
    J

    @dribvurhd This is (32n), which is still O(n). The length of Integer when handle as Byte is 32.


  • 90
    J

    Excellent code. Add some explanation here with one example. Hope this will be helpful.

    public class Solution {
        public int findMaximumXOR(int[] nums) {
            int max = 0, mask = 0;
            for (int i = 31; i >= 0; i--) {
                mask |= (1 << i);
                HashSet<Integer> set = new HashSet<Integer>();
                for (int num : nums) {
                    set.add(num & mask); // reserve Left bits and ignore Right bits
                }
                
                /* Use 0 to keep the bit, 1 to find XOR
                 * 0 ^ 0 = 0 
                 * 0 ^ 1 = 1
                 * 1 ^ 0 = 1
                 * 1 ^ 1 = 0
                 */
                int tmp = max | (1 << i); // in each iteration, there are pair(s) whoes Left bits can XOR to max
                for (int prefix : set) {
                    if (set.contains(tmp ^ prefix)) {
                        max = tmp;
                    }
                }
            }
            return max;
        }
    }
    

    example: Given [14, 11, 7, 2], which in binary are [1110, 1011, 0111, 0010].
    Since the MSB is 3, I'll start from i = 3 to make it simplify.

    1. i = 3, set = {1000, 0000}, max = 1000
    2. i = 2, set = {1100, 1000, 0100, 0000}, max = 1100
    3. i = 1, set = {1110, 1010, 0110, 0010}, max = 1100
    4. i = 0, set = {1110, 1011, 0111, 0010}, max = 1100

  • 0
    L

    @Joyce_Lee said in Java O(n) solution using bit manipulation and HashMap:

    set.add(num & mask);

    Hi Joyce, since only the AND of the current num and the mask is being added to the SET, wouldn't the SET only have 2 values?
    if mask is '1000', then only 1000 and/or 0000
    if mask is '0100', then only 0100 and/or 0000
    I'm trying to fully understand the solution, appreciate any feedback! thanks!


  • 0
    A

    @Joyce_Lee Should the result (max) of last step (4) be 1100?


  • 0
    J

    @alpb0130 Sorry my bad. Just correct it.


  • 0
    J

    @luisfvasq The mask is 1000, 1100, 1110, 1111.


  • 0
    L

    @Joyce_Lee thanks for clarifying!


  • 34
    X

    A XOR B == C
    => C XOR B == A
    => C XOR A == B


  • 0
    R

    @Joyce_Lee Hello, your example is wrong. When i=0, max should be 1100. I stock on this example and realize the number is wrong, but thanks for your explanation.


  • 0
    J

    @robert501128 already changed that. Sorry


  • 44
    R

    I saw deeply and found out a very important xor feature I missed, that is: if a^b=c, then a^c=b, b^c=a. That's why the answer using this code:

                for(int prefix : set){
                    if(set.contains(tmp ^ prefix)) {
                        max = tmp;
                        break;
                    }
                }
    
    

  • 52
    T

    C++ version of your solution with some comments. I have to put the hash set outside the loop otherwise the OJ gives me MLE.

    int findMaximumXOR(vector<int>& nums) {
            int max = 0, mask = 0;
            unordered_set<int> t;
            // 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--){
                // mask contains the bits considered so far
                mask |= (1 << i);
                t.clear();
                // store prefix of all number with right i bits discarded
                for (int n: nums){
                    t.insert(mask & n);
                }
                
                // 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 : t){
                    if (t.find(prefix ^ candidate) != t.end()){
                        max = candidate;
                        break;
                    }
                    
                }
            }
            return max;
        }
    

  • 0
    C

    @Joyce_Lee Thank you for the clear explanation, Joyce.


  • 0
    D

    @robert501128 I have been breaking my head to understand,how XOR of the two number in the array is replaced by this code snippet. I know the trick here revolves around "a^b=c, then a^c=b, b^c=a",but it will be great if you can explain what a,b &c corresponds to in the example which joyce_Lee explained in the previous threads.


  • 0
    T

    @deepaksn1214 read my thread. I think you'll find it helpful.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.