Maximize Total Number of Bits of Pairwise XORs


  • 0
    A

    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


  • 0
    I

    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) {
    					sub.add(superSet.get(idx));
    				}
    				idx++;
    			}
    			if (sub.size() == size) {
    				all.add(sub);
    			}
    		}
    
    		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);
    	}
    

Log in to reply
 

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