Description
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] <= 104
Solutions
This function sorts an array by the number of 1 bits in each number's binary representation, with ties broken by numerical order. It first sorts the array numerically, then creates 17 empty buckets (since a 32-bit number can have at most 32 ones, but the function handles up to 16 based on the array initialization) — one for each possible count of 1 bits. For each number, it converts it to a binary string (e.g., 5 becomes "101"), counts the '1' characters, and places the number in the corresponding bucket (e.g., 5 has two 1s, so it goes in dp[2]). Finally, it flattens the 2D bucket structure back into a single array, which automatically produces the sorted result since the buckets are indexed in order (0, 1, 2, ..., 16).
/**
* @param {number[]} arr
* @return {number[]}
*/
var sortByBits = function(arr) {
arr.sort((a, b) => a - b);
const dp = Array.from({ length: 17 }, () => new Array());
for (const num of arr) {
const ones = num.toString(2).split('').filter(x => x === '1').length;
dp[ones].push(num);
}
return dp.flat(1);
};