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

• 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);
}
``````

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