The challenge
In this example you need to implement a function that sort a list of integers based on it’s binary representation.
The rules are simple:
- sort the list based on the amount of 1’s in the binary representation of each number.
- if two numbers have the same amount of 1’s, the shorter string goes first. (ex: “11” goes before “101” when sorting 3 and 5 respectively)
- if the amount of 1’s is same, lower decimal number goes first. (ex: 21 = “10101” and 25 = “11001”, then 21 goes first as is lower)
Examples:
- Input: [1,15,5,7,3]
- ( in binary strings is:
["1", "1111", "101", "111", "11"])
- ( in binary strings is:
- Output: [15, 7, 3, 5, 1]
- (and after sortByBinaryOnes is:
["1111", "111", "11", "101", "1"])
- (and after sortByBinaryOnes is:
The solution in Java code
Option 1:
import java.util.Arrays;
import static java.util.Comparator.comparing;
import static java.util.Comparator.reverseOrder;
class SortByBinaryOnes{
static Integer[] sort(final Integer[] list) {
return Arrays.stream(list)
.sorted(comparing(Integer::bitCount, reverseOrder())
.thenComparing(Integer::highestOneBit)
.thenComparing(Integer::compare))
.toArray(Integer[]::new);
}
}
Option 2:
import java.util.*;
public class SortByBinaryOnes{
public static Integer[] sort(Integer list[]){
Arrays.sort(list,Comparator.comparingInt(Integer::bitCount).reversed().thenComparing(x->x));
return list;
}
}
Option 3:
import java.util.*;
public class SortByBinaryOnes{
public static Integer[] sort(Integer list[]){
Arrays.sort(list, new Comparator<Integer>(){
@Override
public int compare(Integer x, Integer y){
int c;
c= (Integer.toBinaryString(y).replace("0","")).length() - (Integer.toBinaryString(x).replace("0","")).length();
if (c == 0) c= (Integer.toBinaryString(x)).length() - (Integer.toBinaryString(y)).length();
if (c == 0) c = x.compareTo(y);
return c;
}
});
return (list);
}
}
Test cases to validate our solution
import org.junit.Test;
import static org.junit.Assert.assertEquals;
import org.junit.runners.JUnit4;
public class SortByBinaryOnesTest {
@Test
public void testSort() {
SortByBinaryOnes sortByBinary = new SortByBinaryOnes();
assertEquals(sortByBinary.sort(new Integer[]{1, 3}), new Integer[]{3, 1});
assertEquals(sortByBinary.sort(new Integer[]{1, 2, 3, 4}), new Integer[]{3, 1, 2, 4});
}
}
