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.
1using System;
2using System.Linq;
3
4public class Solution {
5 public int[] SortByBits(int[] arr) {
return arr.OrderBy(x => Convert.ToString(x, 2).Count(c => c == '1')).ThenBy(x => x).ToArray();
}
}The C# solution leverages LINQ to sort the array first by the number of 1's in the binary representation and then by the value itself. It converts each number to binary using Convert.ToString and counts the 1's using Count.