Sort Integers by The Number of 1 Bits — Problem & Solution
Sort Integers by The Number of 1 Bits solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Sort Integers by The Number of 1 Bits is an easy coding problem on arrays, sorting and bit manipulation, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Arrays, Sorting, Bit Manipulation, Counting
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an integer array arr, sort it in ascending order by the number of 1 bits in each value's binary representation. Values with the same bit count are sorted by their numeric value, ascending.
Example 1
Input: arr = [0,1,2,3,4,5,6,7,8]
Output: [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]
Explanation: Every value has exactly one set bit.
Example 3
Input: arr = [3,5,6]
Output: [3,5,6]
Constraints
1 <= arr.length <= 400 <= arr[i] <= 10000
Hints for Sort Integers by The Number of 1 Bits
Hint 1
Count set bits by repeatedly testing the lowest bit and shifting right.
Hint 2
Sort with a comparator: bit count first, then the value itself.
Hint 3
x & (x - 1)clears the lowest set bit, giving a loop that runs once per set bit.
How to solve Sort Integers by The Number of 1 Bits
Sort with key (popcount, value).
Approach
- Compute each value's set-bit count.
- Sort by
(bits, value).
Why it works
The composite key implements the two-level order directly.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
x & (x - 1)clears the lowest set bit — a loop that runs once per bit.
Reference solution
Python
def sortByBits(arr):
return sorted(arr, key=lambda x: (bin(x).count("1"), x))Java
public static int[] sortByBits(int[] arr) {
Integer[] boxed = new Integer[arr.length];
for (int i = 0; i < arr.length; i++) boxed[i] = arr[i];
Arrays.sort(boxed, (a, b) -> {
int pa = Integer.bitCount(a), pb = Integer.bitCount(b);
if (pa != pb) return pa - pb;
return a - b;
});
int[] out = new int[arr.length];
for (int i = 0; i < arr.length; i++) out[i] = boxed[i];
return out;
}C++
vector<int> sortByBits(vector<int>& arr) {
vector<int> out = arr;
sort(out.begin(), out.end(), [](int a, int b) {
int pa = __builtin_popcount((unsigned) a);
int pb = __builtin_popcount((unsigned) b);
if (pa != pb) return pa < pb;
return a < b;
});
return out;
}JavaScript
var sortByBits = function(arr) {
const popcount = function(x) {
let count = 0, v = x;
while (v > 0) {
count += v & 1;
v >>>= 1;
}
return count;
};
return arr.slice().sort(function(a, b) {
const pa = popcount(a), pb = popcount(b);
return pa !== pb ? pa - pb : a - b;
});
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms