Sort Integers by The Number of 1 Bits

Problem 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.

Key Insights

• The problem requires sorting based on two criteria: the number of 1 bits in the binary representation of integers and their natural order for those with the same number of 1 bits.
• The number of 1 bits can be determined using bit manipulation techniques.
• Python’s built-in sorting functions can be used effectively with custom sorting keys.

Space and Time Complexity

Time Complexity: O(n log n) - due to the sorting operation. Space Complexity: O(n) - for storing the sorted array.

Solution

To solve the problem, we will utilize a custom sorting function. The key to this function will be a tuple consisting of two elements: the first element will be the count of 1 bits in the binary representation of each integer, and the second element will be the integer itself. By sorting using this tuple, we can achieve the desired order in one pass.

1. Use a lambda function to return a tuple (number of 1 bits, integer value) for each element.
2. Utilize Python's built-in sorted() function to perform the sorting based on this tuple.
3. Return the sorted list.

Code Solutions