Watch 10 video solutions for Sort Integers by The Number of 1 Bits, a easy level problem involving Array, Bit Manipulation, Sorting. This walkthrough by codestorywithMIK has 15,114 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 104Problem Overview: Given an array of integers, sort the numbers based on how many 1 bits appear in their binary representation. If two numbers have the same number of set bits, order them by their numeric value.
The task combines Bit Manipulation with Sorting. The core operation is computing the popcount (number of set bits) for each integer and using it as the primary sorting key.
Approach 1: Sorting with Custom Key Function (O(n log n) time, O(1) extra space)
Sort the array using a custom comparator or key function. The key returns a pair: (bitCount(x), x). The first element sorts numbers by the number of set bits. The second element ensures values with the same bit count are ordered numerically. Most languages expose built-in popcount utilities such as bin(x).count('1') in Python, Integer.bitCount() in Java, or __builtin_popcount() in C++. The sorting algorithm handles the ordering once the key is defined. Time complexity is O(n log n) due to sorting, while space complexity is O(1) or O(log n) depending on the sorting implementation.
Approach 2: Counting Bits and Sorting (O(n log n) time, O(n) space)
First compute the bit count for every number and store it alongside the value, typically as pairs like (bitCount, value). Bit counts can be calculated using Kernighan’s algorithm, built-in popcount functions, or simple bit shifting. After building this list, sort it using the pair structure so that the array is ordered by bit count first and number second. Finally extract the sorted numbers back into the result array. The preprocessing pass takes O(n * B) where B is the number of bits (at most 32 for typical integers), followed by sorting in O(n log n). Space complexity becomes O(n) due to the auxiliary array.
Both approaches rely on the same insight: treat the bit count as the primary sorting metric and the integer value as the tie breaker. The problem mainly tests familiarity with Array handling and popcount operations.
Recommended for interviews: The custom key sorting approach is the expected solution. It is concise, leverages built-in popcount functions, and clearly expresses the intended ordering rule. Mentioning how to compute set bits (for example with Kernighan’s trick) shows deeper understanding of bit manipulation even if the implementation uses a built-in method.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting with Custom Key (popcount) | O(n log n) | O(1) - O(log n) | Best general solution. Uses built-in bit count and concise comparator. |
| Counting Bits then Sorting Pairs | O(n log n) | O(n) | Useful when computing or caching bit counts separately before sorting. |