New update is available. Click here to update.

Sort An Array According To The Count Of Set Bits

Contributed by
Anup Kumar Singh
Last Updated: 23 Feb, 2023
Medium
0/80
Avg time to solve 25 mins
Success Rate 80 %
Share
18 upvotes

Problem Statement

Suggest Edit

Note :

``````1. If any two numbers have the same count of set bits, then in the sorted array they will appear in the order in which they appear in the original array. For example, let the array be { 2, 4, 3}, in this case, both 2 and 4 have the same number of set bits so the answer will be {3, 2, 4} and not {3, 4, 2}, because in the original array 2 appears before 4.

2. The array may contain duplicate elements.
``````
Detailed explanation ( Input/output format, Notes, Images )
Constraints :
``````1 <= T <= 50
1 <= N <= 10^4
1 <= arr[i] <= 10^9
``````
Sample Input 1 :
``````1
3
2 4 8
``````
Sample Output 1 :
``````2 4 8
``````
Explanation for sample input 1 :
``````The binary representation of 2,4 and 8 will be {10, 100, 1000}, respectively. The count of set bits is one for all the three numbers so the sorted order will be {2, 4, 8}.
``````
Sample Input 2 :
``````1
3
4 3 8
``````
Sample Output 2 :
``````3 4 8
``````
Explanation for sample input 2 :
``````The binary representation of 3,4 and 8 will be {11, 100, 1000}, respectively. The count of set bits for 3,4, and 8 is 2,1 and 1 respectively. So the sorted order will be {3, 4, 8}.
``````
Auto
Console