Sponsored
Sponsored
The basic idea is to use a custom key that calculates two parameters for sorting: the number of 1 bits in the binary representation and the integer value itself. This dual-key approach allows us to first sort by the number of 1 bits and then by the integer values in ascending order by default.
Time Complexity: O(n log n) due to the sorting operation.
Space Complexity: O(n) for storing the sorted array.
1def sortByBits(arr):
2 return sorted(arr, key=lambda x: (bin(x).count('1'), x))This solution uses Python's built-in sorted function with a custom key. bin(x).count('1') counts the number of 1 bits in the binary representation, and we sort the array using a tuple as the key where the first element is the number of 1 bits and the second element is the number itself.
Another approach is to first count the number of 1 bits for each integer and create a pair of this count and the integer. Then, sort the array of these pairs according to the count and original value.
Time Complexity: O(n log n) for sorting.
Space Complexity: O(1), sorting is done in place.
1#include <stdio.h>
2#include
In this C language solution, we define a helper function countBits to calculate the number of 1 bits. The array is sorted using qsort with compare function for customization over number of bits and values.