Problem
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.
Examples
Example 1
|
|
Example 2
|
|
Constraints
1 <= arr.length <= 500
0 <= arr[i] <= 10^4
Solution
Method 1 - Custom Sorting with Bit Counting
Intuition: Count the number of 1 bits in each number’s binary representation and sort primarily by bit count, secondarily by the number value itself.
Approach:
- For each number, count the number of 1 bits using bit manipulation
- Create pairs of (bit_count, number) or use custom comparator
- Sort by bit count first, then by number value for ties
- Extract the sorted numbers
Code
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Complexity
- ⏰ Time complexity:
O(n log n + n * k)
where n is array length, k is average number of bits (≤ 32) - 🧺 Space complexity:
O(1)
for in-place sorting (O(n) if creating new array)