Given two integers m and n where m < n find the maximum pair-wise xor sum. The question is how to choose m distinct integers from 1 to n such that using those m numbers yields the maximum pair-wise xor sum.

The maximum pair-wise xor sum is calculated on a set of integers x as F(x) = sum( number_of_bits( xor(x[i], x[j]) ) for i = 1 to k, j = (i + 1) to k )

For example: if x = [4, 6, 8], let CB(num) return number of 1 bits in the number. F(x) = CB(4 xor 6) + CB(4 xor 8) + CB(6 xor 8) = CB(2) + CB(12) + CB(14) = 1 + 2 + 3 = 6

The brute force solution could be to generate all subsets of size m and then computing the pair-wise xor sum for each and then taking the maximum out of those. That would be exponential in terms of time.

  • 2
    $\begingroup$ The question is missing? $\endgroup$ – Evil Feb 13 '18 at 3:41
  • $\begingroup$ The question is to return the set of m numbers that give the max pair-wise xoxr sum. $\endgroup$ – IRI7 Feb 13 '18 at 23:22
  • $\begingroup$ This is the task that you were given (without attribution), not a proper question. It seems that to find maximum pairwise xor sum (which is pairwise Hamming distance?) partitioning is not needed, if it were at least using xor (Hamming) properties would vastly reduce the set. So what have you tried so far? I think the result could be calculated in constant time. $\endgroup$ – Evil Feb 14 '18 at 5:37
  • 1
    $\begingroup$ So far I tried thinking about generating all the pairs possible for integers from 1 to n and then sorting them by their xor bit sum. Then taking the first m distinct numbers from those pairs. However that didn't yield the maximum possible sum. $\endgroup$ – IRI7 Feb 15 '18 at 0:14
  • $\begingroup$ Your approach is a bit too greedy, also are you sure that bit xor sum results could be sorted? Have you tried calculating result wthout partitioning numbers? $\endgroup$ – Evil Feb 15 '18 at 17:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.