Sort by binary ones in Java

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:

  1. sort the list based on the amount of 1’s in the binary representation of each number.
  2. 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)
  3. 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"])
  • Output: [15, 7, 3, 5, 1]
    • (and after sortByBinaryOnes is: ["1111", "111", "11", "101", "1"])

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); } }
Code language: Java (java)

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; } }
Code language: Java (java)

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); } }
Code language: Java (java)

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}); } }
Code language: Java (java)
Tags:
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments