Sort Integers by The Number of 1 Bits
Problem
Sort the array in ascending order by the number of 1's in their binary representation. If two numbers have the same count of 1's, sort them by value (ascending).
arr = [0,1,2,3,4,5,6,7,8][0,1,2,4,8,3,5,6,7]def sort_by_bits(arr):
return sorted(arr, key=lambda x: (bin(x).count('1'), x))function sortByBits(arr) {
function pop(x) { let c = 0; while (x) { c += x & 1; x >>>= 1; } return c; }
return arr.slice().sort((a, b) => pop(a) - pop(b) || a - b);
}class Solution {
public int[] sortByBits(int[] arr) {
Integer[] a = new Integer[arr.length];
for (int i = 0; i < arr.length; i++) a[i] = arr[i];
Arrays.sort(a, (x, y) -> {
int d = Integer.bitCount(x) - Integer.bitCount(y);
return d != 0 ? d : x - y;
});
int[] r = new int[arr.length];
for (int i = 0; i < arr.length; i++) r[i] = a[i];
return r;
}
}vector sortByBits(vector arr) {
sort(arr.begin(), arr.end(), [](int a, int b) {
int pa = __builtin_popcount(a), pb = __builtin_popcount(b);
return pa != pb ? pa < pb : a < b;
});
return arr;
} Explanation
We need to sort the array primarily by how many 1 bits each number has, and when two numbers tie on that count, break the tie by their actual value.
Python makes this a one-liner: sorted(arr, key=lambda x: (bin(x).count('1'), x)). The key is a tuple, and Python compares tuples left to right — so it first compares popcounts, and only looks at x itself when the popcounts are equal.
Here bin(x).count('1') just counts the 1 characters in the binary string of x, which is its number of set bits.
Because the sort is stable and we provide a complete tie-breaker, the ordering is fully determined and ascending in both keys.
Example: arr = [0,1,2,3,4,5,6,7,8]. Popcounts are 0 for 0; 1 for 1,2,4,8; 2 for 3,5,6; and 3 for 7. Grouping by count and sorting by value within each group gives [0,1,2,4,8,3,5,6,7].