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] <= 104The 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.
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.
Java
C++
Time Complexity: O(n log n) due to the sorting operation.
Space Complexity: O(n) for storing the sorted array.
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.
This JavaScript solution uses the Array.sort method with a custom comparator. It calculates the count of 1's by converting the number to binary and counting the 1's using string manipulation.
C#
C
Time Complexity: O(n log n) for sorting.
Space Complexity: O(1), sorting is done in place.
| Approach | Complexity |
|---|---|
| Sorting with Custom Key Function | Time Complexity: O(n log n) due to the sorting operation. |
| Counting Bits and Sorting | Time Complexity: O(n log n) for sorting. |
Number of 1 Bits - Leetcode 191 - Python • NeetCode • 155,493 views views
Watch 9 more video solutions →Practice Sort Integers by The Number of 1 Bits with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor