Sort by Number of Set Bits
EasyPractice library · +10 XPsortingcounting sortbit manipulation
Given a list of non-negative integers, sort them in non-decreasing order based on the number of set bits (1s) in their binary representation. If two numbers have the same number of set bits, sort them in non-decreasing order of their values.
Input
The first line contains an integer N. The second line contains N space-separated non-negative integers.
Output
Print the N integers in the sorted order, separated by spaces.
Constraints
1 <= N <= 1000. Each integer will be between 0 and 10^9.
Time limit 1 s (native code; slower languages get more)Memory 256 MB13 hidden tests
Example 1
Input
5 1 2 3 4 5
Output
1 2 4 3 5
Binary: 1(1), 10(1), 11(2), 100(1), 101(2). Sorted by bits then value: [1, 2, 4, 3, 5]
Example 2
Input
4 8 16 4 1
Output
1 4 8 16
Binary: 1000(1), 10000(1), 100(1), 1(1). All have 1 set bit, so sort by value: [1, 4, 8, 16]
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
5 1 2 3 4 5
Example 2 input
4 8 16 4 1