Sort Integers by The Number of 1 Bits

Explore Solutions in Other Languages

Problem Description

Ah, the classic dilemma of sorting integers by the number of 1 bits in their binary representation! It’s like trying to organize a party where you only invite the guests with the most interesting stories—except in this case, the stories are just a bunch of 1s and 0s.

Imagine you have a group of friends, and you want to arrange them based on how many times they’ve said “yes” to your crazy ideas (1s) versus how many times they’ve said “no” (0s). The more “yeses” they have, the closer they get to the front of the line. But wait! If two friends have the same number of “yeses,” you’ll have to sort them by their names alphabetically.

In the world of coding, this translates to sorting integers based on the number of 1 bits in their binary form, and if there’s a tie, sorting them by their actual values.

Code Solution


class Solution {
  public int[] sortByBits(int[] arr) {
    Integer[] A = Arrays.stream(arr).boxed().toArray(Integer[] ::new);
    Arrays.sort(A,
                (a, b)
                    -> Integer.bitCount(a) == Integer.bitCount(b)
                           ? a - b
                           : Integer.bitCount(a) - Integer.bitCount(b));
    return Arrays.stream(A).mapToInt(Integer::intValue).toArray();
  }
}

Approach

The approach here is quite straightforward. First, we convert the integer array into an array of Integer objects. This allows us to use the Arrays.sort() method with a custom comparator. The comparator checks the number of 1 bits in each integer using Integer.bitCount(). If two integers have the same number of 1 bits, we sort them by their actual values. Finally, we convert the sorted Integer array back to an int array to return the result.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n log n)
Space Complexity	O(n)

Real-World Example

Think of a group of people trying to get into a club. The bouncers (our sorting algorithm) only let in those who have the most “yes” votes (1 bits). If two people have the same number of “yes” votes, they’ll let in the one with the better outfit (lower integer value). This ensures that the club is filled with the most enthusiastic party-goers first!