C solution beats 100% for the moment based on @bartoszkp's


  • 0
    E

    The concept is very like quick sort.

    // return index of the beginning of the second part
    // so the two partitions should be l~ret-1 and ret~r
    int qBitPartition(int* a, int l, int r, int bc) {
        if (a == NULL || l > r || bc >= 32 || bc < 0) return -1; 
        int i = l;
        int j = r;
        int ret = -1; 
        while (i < j) {
            while (i < j && 1 != ((a[i] >> bc) & 0x01)) i++;
            while (i < j && 0 != ((a[j] >> bc) & 0x01)) j--;
            if (i < j) {
                a[i] ^= a[j];
                a[j] ^= a[i];
                a[i] ^= a[j];
            }   
        }   
        ret = i;
        // in case all elements fall into the first part
        if (0 == ((a[i] >> bc) & 0x01)) ret++;
    
        /*  
        printf("(%d)[ ", bc);
        for (int i = l; i <= ret-1; i++) {
            printf("%02X ", a[i]);
        }
        printf("] [ ");
        for (int i = ret; i <= r; i++) {
            printf("%02X ", a[i]);
        }
        printf("]\n");
        */
    
        return ret;
    }
    
    // one number is selected from l1~r1
    // the other numbser is selected from l2~r2
    int findPartitionMaxXor(int* a, int l1, int r1, int l2, int r2, int bc) {
        if (l1 > r1 || l2 > r2) return 0;
        // in case there are duplicate numbers
        if (bc == 0) return a[l1] ^ a[l2];
        if (l1 == r1 && l2 == r2) return a[l1] ^ a[l2];
        bc--;
        int max1 = 0;
        int max2 = 0;
        // find next available partition, jump over all zero bits
        while(bc >= 0) {
            int p1 = qBitPartition(a, l1, r1, bc);
            int p2 = qBitPartition(a, l2, r2, bc);
            if ((p1-1 >= l1) && (r2 >= p2) ||
                    (r1 >= p1) && (p2-1 >= l2)) {
                max1 = findPartitionMaxXor(a, l1, p1-1, p2, r2, bc);
                max2 = findPartitionMaxXor(a, p1, r1, l2, p2-1, bc);
                break;
            }   
            bc--;
        } 
        return max1 > max2 ? max1 : max2;
    }
    
    int findMaximumXOR(int* nums, int numsSize) {
        int bc = 31; 
        int p = 0;
        // we must find a no empty partition first
        while (bc >= 0) {
            p = qBitPartition(nums, 0, numsSize-1, bc);
            if (p > 0 && p < numsSize) break;
            bc--;
        }
        return findPartitionMaxXor(nums, 0, p-1, p, numsSize-1, bc);
    }
    

Log in to reply
 

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