Wednesday, March 18, 2015

BinaryCardinality

Problem:

TopCoder Problem Statement - BinaryCardinality
Single Round Match 166 Round 1 - Division I, Level One
Single Round Match 166 Round 1 - Division II, Level Two

Overview:

Sort an arrray of integers based on their binary cardinality. Binary cardinality is the number of 1's in the binary representation of the number.

Java Source:
01: import java.util.Arrays;
02: import java.util.Comparator;
03: 
04: public class BinaryCardinality {
05: 
06:     private class BinaryCardinalityComparator implements Comparator  {
07: 
08:         /*
09:         * Compares the binary cardinality of the two numbers.  If that's
10:         * equal, then compare the value of the numbers themselves.
11:         */
12:         @Override
13:         public int compare(Integer o1, Integer o2) {
14: 
15:             int c1 = binaryCardinality(o1);
16:             int c2 = binaryCardinality(o2);
17: 
18:             if (c1 < c2) return -1;
19:             if (c2 < c1) return 1;
20: 
21:             return o1.compareTo(o2);
22:         }
23: 
24:         /*
25:         * Counts the number of 1's in the binary representation of the number.
26:         */
27:         public int binaryCardinality(Integer i)  {
28: 
29:             int c = 0;
30: 
31:             while (i > 0)  {
32:                 if ((i & 1) == 1) c++;
33:                 i = i >> 1;
34:             }
35: 
36:             return c;
37:         }
38:     }
39: 
40:     public int[] arrange(int[] numbers) {
41: 
42:         // Convert array of ints to an array of Integer
43:         Integer[] numbersAsIntegers = new Integer[numbers.length];
44: 
45:         for (int i = 0; i < numbers.length; i++)  {
46:             numbersAsIntegers[i] = numbers[i];
47:         }
48: 
49:         // Sort the numbers using our custom Comparator.
50:         Arrays.sort(numbersAsIntegers, new BinaryCardinalityComparator());
51: 
52:         // Convert array of Integer back to array of ints.
53:         int[] result2 = new int[numbers.length];
54: 
55:         for (int i = 0; i < numbers.length; i++)  {
56:             result2[i] = numbersAsIntegers[i];
57:         }
58: 
59:         return result2;
60:     }
61: 
62: }
63
Notes:

The class BinaryCardinalityComparator handles comparing two Integers based on their binary cardinality. This is done by calling binaryCardinality() on each number and checking the results. If the cardinality is the same, then we defer to Integer.compareTo() method to sort the numbers based on value. The binaryCardinality() method counts the number of 1's by examining the right-most bit, and then performing a bit-shift to the right. This loop continues until the value of the number eventually becomes 0.

By implementing our own Comparator, we can now use the built in Arrays.sort() method to sort the numbers. We simply pass an instance of our comparator as a second paramter.

The trouble with our BinaryCardinalityComparator class is that it requires objects (Integer) rather than ints. So, the arrange() method must first convert the given int[] into an Integer[]. It then performs the sort, and finally converts the Integer[] back into an int[].

No comments:

Post a Comment