# Maximize Total Number of Bits of Pairwise XORs

• Input: m, n (where m < n)
Output: Give m distinct integers from 1 to n that maximizes the total number of 1-bits in pairwise XORs (explained below).

Total number of bits in all pairwise XORs given an array of integers x:
F(x) = sum( number_of_bits( xor(x[i], x[j]) ) for i = 1 to m, j = (i + 1) to m )

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

• The best I could do is brute force:

``````	private void maxBits(List<Integer> superSet, int size) {
int total = 1 << superSet.size(); // 2^ superset size
List<List<Integer>> all = new ArrayList<List<Integer>>();
for (int i = 0; i < total; i++) {
List<Integer> sub = new ArrayList<Integer>();
int idx = 0;
// for each bit that is set in the ith binary number
// add that many elements from the original set into a new subset
for (int j = i; j > 0; j >>= 1) {
if ((j & 1) == 1) {
}
idx++;
}
if (sub.size() == size) {
}
}

System.out.println("Number of subsets of size " + size + " is " + all.size());
int maxSum = 0;
List<Integer> maxSubset = null;
for (List<Integer> subset : all) {

int sum = 0;
for (int i = 0; i < subset.size() - 1; i++) {
for (int j = i + 1; j < subset.size(); j++) {
int xor = subset.get(i) ^ subset.get(j);
int sumBits = countBits(xor);
sum += sumBits;
}
}
if (maxSum < sum) {
maxSum = sum;
maxSubset = subset;
}
}
System.out.println("max sum is " + maxSum + " formed by subset " + maxSubset);
}
``````

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