Sort Integers By The Number Of 1 Bits - Leetcode Solution

Problem:

Given an integer array nums. Sort the array according to the number of 1's in the binary representation of each number in nums.

Example 1:

Input: nums = [0,1,2,3,4,5,6,7,8] Output: [0,1,2,4,8,3,5,6,7] Explanation: [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: nums = [1024,512,256,128,64,32,16,8,4,2,1] Output: [1,2,4,8,16,32,64,128,256,512,1024] Explanation: All integers have 1 bit in the binary representation, you should just sort them in ascending order.

Approach:

The approach to the solution of this problem is pretty simple. We can use a counting sort-like algorithm to sort the numbers in the array. We can count the number of 1 bits in each number and then place each number in the corresponding bucket. Finally, we can append all the sorted buckets to get the sorted array. We can use a dictionary or a list of buckets to store the elements.

For example, if nums = [0,1,2,3,4,5,6,7,8], we can count the number of 1 bits in each of these numbers as follows:

Number: 0, Binary: 00, Count of 1's: 0 Number: 1, Binary: 01, Count of 1's: 1 Number: 2, Binary: 10, Count of 1's: 1 Number: 3, Binary: 11, Count of 1's: 2 Number: 4, Binary: 100, Count of 1's: 1 Number: 5, Binary: 101, Count of 1's: 2 Number: 6, Binary: 110, Count of 1's: 2 Number: 7, Binary: 111, Count of 1's: 3 Number: 8, Binary: 1000, Count of 1's: 1

Then we can create buckets for each count of 1's as follows:

buckets = [[], [], [], [], [], [], [], []]

We can then append each number to its corresponding bucket and sort the elements in each bucket.

nums = [0,1,2,3,4,5,6,7,8] buckets = [[], [], [], [], [], [], [], []]

for num in nums: count = bin(num).count('1') buckets[count].append(num)

sorted_nums = [] for bucket in buckets: sorted_nums += sorted(bucket)

return sorted_nums

We can further simplify the code by using a lambda function as the key to the sorted() function, which returns the count of 1's in the binary representation of the number.

Code:

Here's the Python code for the solution:

def sortIntegersByBits(nums: List[int]) -> List[int]: buckets = [[] for _ in range(14)] for num in nums: count = bin(num).count('1') buckets[count].append(num) return [num for bucket in buckets for num in sorted(bucket)]

1