Similar Problems
Similar Problems not available
Sort An Array according to number of set bits - Leetcode Solution
LeetCode: Sort An Array according to number of set bits Leetcode Solution
Difficulty: Easy
Topics: sorting
Sort An Array according to number of set bits
Given an integer array arr. You have to 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 sorted array.
Example 1:
Input: [0,1,2,3,4,5,6,7,8]
Output: [0,1,2,4,8,3,5,6,7]
Example 2:
Input: [1,5,7,13,17,21,23,25]
Output: [1,5,17,7,13,21,25,23]
Constraints:
1 <= arr.length <= 5000 <= arr[i] <= 10^4
Solution:
This is not a usual solution of just sorting the numbers in ascending, instead we need to see number of 1 bit in the number then sort them according to the number of 1 bit. We first built a list. Sorting can be done using comparator and counting is done using bit mask and by bit shifting strategy. We at last transform our resulting values into an array.
Complexity Analysis:
-
Time Complexity: O(n)
-
Space Complexity: O(n)
Sort An Array according to number of set bits Solution Code
1