New update is available. Click here to update.

Problem

Submissions

Solution

New

Discuss

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 %

18 upvotes

Problem Statement

Suggest Edit

You are given an array consisting of N positive integers, and your task is to sort the array in decreasing order of count of set bits in the binary representation of the integers present in the array.

In other words, you have to modify the array such that an integer with more number of set bits should appear before the integer which has lesser number of set bits in its binary representation.

The number of set bits is nothing but the number of 1s present in the binary representation of the integer. For example, the number of set bits in 5(0101) is equal to 2.

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 )

Input Format :

The first line of input contains the integer T, denoting the number of test cases.

The first line of each test case contains an integer N, denoting the size of the array.

The second line of each test case contains N space-separated integers denoting the array elements.

Output Format :

The only line of output of each test case consists of N space-separated integers, the elements of the array in the order as described in the problem statement

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function. Also, you need to modify the given array in-place.

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

Sorting Notes

Introduction to Sorting

Selection Sort

Bubble Sort

Insertion Sort

Merge Sort

Quick Sort

Counting Sort

Problems Based on Sorting

Sort by Kth bit

Sort an array in wave form

Sort an array according to the count of set bits

Relative Sorting

Sort a half-sorted array

Binary Array Sorting

Minimum number of swaps required to sort an array

Sort An Array According To The Count Of Set Bits

Problem Statement

You are given an array consisting of N positive integers, and your task is to sort the array in decreasing order of count of set bits in the binary representation of the integers present in the array.

In other words, you have to modify the array such that an integer with more number of set bits should appear before the integer which has lesser number of set bits in its binary representation.

The number of set bits is nothing but the number of 1s present in the binary representation of the integer. For example, the number of set bits in 5(0101) is equal to 2.

Note :

Input Format :

Output Format :

Note :

Constraints :

Sample Input 1 :

Sample Output 1 :

Explanation for sample input 1 :

Sample Input 2 :

Sample Output 2 :

Explanation for sample input 2 :