Sort List by Hamming Weight

You are given a lists of non-negative integers nums. Sort the list in ascending order by the number of 1s in binary representation for each number. If there are ties in the number of 1s, then break ties by their value in ascending order.

Constraints

• 0 ≤ n ≤ 100,000 where n is the length of nums

https://binarysearch.com/problems/Sort-List-by-Hamming-Weight

Examples

Example 1

Input

• nums = [3, 1, 4, 7]

Output

• answer = [1, 4, 3, 7]

Explanation

1 and 4 both have one 1s but 1 comes earlier since it has lower value. 3 has two 1s. And 7 has three 1s.

Solution