Scale Engineer

Sort Integers by The Number of 1 Bits

Easy
#1258Time: O(N * K * log N), where `N` is the number of elements in the array and `K` is the number of bits in an integer. The `log N` factor comes from the sort, and for each comparison, we perform a `O(K)` operation to count bits. Since `K` is small (at most 14 for the given constraints), this is feasible but not optimal.Space: O(N) to store the boxed `Integer` array. The sorting algorithm itself might use `O(log N)` (quicksort) or `O(N)` (mergesort/timsort) auxiliary space.3 companies
Patterns
Bit ManipulationCounting
Algorithms
Sorting
Data structures
Array
Companies
AccentureJ.P. MorganMapbox

Prompt

You are given an integer array arr. Sort the integers in the array in ascending order by the number of 1's in their binary representation and in case of two or more integers have the same number of 1's you have to sort them in ascending order.

Return the array after sorting it.

 

Example 1:

Input: arr = [0,1,2,3,4,5,6,7,8]
Output: [0,1,2,4,8,3,5,6,7]
Explantion: [0] is the only integer with 0 bits.
[1,2,4,8] all have 1 bit.
[3,5,6] have 2 bits.
[7] has 3 bits.
The sorted array by bits is [0,1,2,4,8,3,5,6,7]

Example 2:

Input: arr = [1024,512,256,128,64,32,16,8,4,2,1]
Output: [1,2,4,8,16,32,64,128,256,512,1024]
Explantion: All integers have 1 bit in the binary representation, you should just sort them in ascending order.

 

Constraints:

  • 1 <= arr.length <= 500
  • 0 <= arr[i] <= 104

Approaches

3 approaches with complexity analysis and trade-offs.

This approach involves using the standard library's sorting function but providing a custom comparison logic. The comparison logic first calculates the number of set bits (1s) for each of the two numbers being compared and then uses these counts as the primary sorting key. The numbers themselves are used as the secondary sorting key for tie-breaking.

Algorithm

  • Create a helper function countSetBits(int n) that iteratively counts the set bits. A simple way is to loop, check the last bit with n & 1, and right-shift n (n >>= 1). A more optimized way is using Brian Kernighan's algorithm (n &= (n - 1)).
  • Convert the input int[] arr to an Integer[] array to allow for sorting with a custom comparator.
  • Use Arrays.sort() on the Integer[] array, providing a custom Comparator.
  • The Comparator's compare(a, b) method will:
    • a. Calculate countA = countSetBits(a).
    • b. Calculate countB = countSetBits(b).
    • c. If countA is different from countB, return countA - countB to sort by bit count.
    • d. Otherwise, return a - b to sort by value as a tie-breaker.
  • Copy the sorted Integer elements back into the original int[] arr.

Walkthrough

The core of this method is a custom Comparator. When the sorting algorithm needs to compare two integers, a and b, the comparator is invoked. Inside the comparator, we first need a helper function, say countSetBits(n), to count the 1s in the binary representation of an integer. This can be done by repeatedly checking the last bit with n & 1 and right-shifting the number (n >>= 1) until it becomes zero. We call this helper function for both a and b to get bitCountA and bitCountB. If bitCountA is not equal to bitCountB, we sort based on the bit counts. If the bit counts are the same, we sort based on the integer values themselves. Since the input array arr contains primitive ints, we first need to convert it to an array of Integer objects to use a custom Comparator with Arrays.sort(). After sorting, we convert it back to an int[].

class Solution {    private int countSetBits(int n) {        int count = 0;        while (n > 0) {            n &= (n - 1); // Brian Kernighan's algorithm            count++;        }        return count;    }     public int[] sortByBits(int[] arr) {        Integer[] boxedArr = new Integer[arr.length];        for (int i = 0; i < arr.length; i++) {            boxedArr[i] = arr[i];        }         Arrays.sort(boxedArr, (a, b) -> {            int countA = countSetBits(a);            int countB = countSetBits(b);            if (countA != countB) {                return countA - countB;            } else {                return a - b;            }        });         for (int i = 0; i < arr.length; i++) {            arr[i] = boxedArr[i];        }        return arr;    }}

Complexity

Time

O(N * K * log N), where `N` is the number of elements in the array and `K` is the number of bits in an integer. The `log N` factor comes from the sort, and for each comparison, we perform a `O(K)` operation to count bits. Since `K` is small (at most 14 for the given constraints), this is feasible but not optimal.

Space

O(N) to store the boxed `Integer` array. The sorting algorithm itself might use `O(log N)` (quicksort) or `O(N)` (mergesort/timsort) auxiliary space.

Trade-offs

Pros

  • Conceptually straightforward and easy to understand.

  • Leverages the standard library's powerful and stable sorting capabilities.

Cons

  • Less efficient due to the repeated calculation of bit counts for the same numbers during the sorting process.

  • Requires converting the primitive int[] to an Integer[], which introduces memory and performance overhead due to boxing.

Solutions

class Solution {public  int[] sortByBits(int[] arr) {    int n = arr.length;    for (int i = 0; i < n; ++i) {      arr[i] += Integer.bitCount(arr[i]) * 100000;    }    Arrays.sort(arr);    for (int i = 0; i < n; ++i) {      arr[i] %= 100000;    }    return arr;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem