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 <= 5000 <= arr[i] <= 104The key idea in #1356 Sort Integers by The Number of 1 Bits is to sort integers based on the number of set bits (1s) in their binary representation. This value is often called the bit count or Hamming weight. For example, the number 7 (binary 111) has three set bits, while 3 (binary 11) has two.
A common strategy is to compute the number of set bits for each element and then perform a custom sort. The primary sorting key is the bit count, and if two numbers have the same number of 1 bits, they should be ordered by their numeric value. Most languages provide a built-in operation such as popcount or bitCount to efficiently count bits.
You can implement this using a sorting function with a custom key like (bitCount(x), x). This avoids manually writing a comparator and keeps the implementation clean. The overall complexity is dominated by sorting, while bit counting is done in constant or near-constant time per number.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Custom Sort Using Bit Count Key | O(n log n) | O(1) or O(n) depending on sorting implementation |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Simulate the problem. Count the number of 1's in the binary representation of each integer.
Sort by the number of 1's ascending and by the value in case of tie.
The basic idea is to use a custom key that calculates two parameters for sorting: the number of 1 bits in the binary representation and the integer value itself. This dual-key approach allows us to first sort by the number of 1 bits and then by the integer values in ascending order by default.
Time Complexity: O(n log n) due to the sorting operation.
Space Complexity: O(n) for storing the sorted array.
1import java.util.Arrays;
2
3public static int[] sortByBits(int[] arr) {
4 return Arrays.stream(arr)
5 .boxed()
6 .sorted((a, b) -> Integer.bitCount(a) == Integer.bitCount(b) ? a - b : Integer.bitCount(a) - Integer.bitCount(b))
7 .mapToInt(i -> i)
8 .toArray();
9}In this Java solution, we convert the integer array to a stream of boxed Integers, sort them using a custom comparator based on the count of 1-bits in their binary representation and then convert the sorted stream back to an int array.
Another approach is to first count the number of 1 bits for each integer and create a pair of this count and the integer. Then, sort the array of these pairs according to the count and original value.
Time Complexity: O(n log n) for sorting.
Space Complexity: O(1), sorting is done in place.
1function sortByBits(arr) {
2Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
You can count set bits using built-in functions like __builtin_popcount in C++, Integer.bitCount in Java, or bin(x).count('1') in Python. Another common technique is Brian Kernighan’s algorithm, which repeatedly removes the lowest set bit until the number becomes zero.
Yes, this problem is a common beginner-friendly interview question that tests understanding of bit manipulation and custom sorting. It is often used to assess how well candidates combine multiple concepts like arrays, bit operations, and sorting.
The problem primarily uses arrays along with a sorting mechanism. The sorting algorithm relies on a custom key or comparator that evaluates the number of set bits and the integer value.
The optimal approach is to sort the array using the number of set bits in each integer as the primary key and the integer value as the secondary key. Most languages provide a built-in bit counting function such as popcount, which makes this approach efficient and concise.
This JavaScript solution uses the Array.sort method with a custom comparator. It calculates the count of 1's by converting the number to binary and counting the 1's using string manipulation.