Problem Brief
Cardinality Sorting
FULLTIMEOA
The binary cardinality of a number is the total number of 1's it contains in its binary representation. For example, the decimal integer 20 corresponds to the binary number 10100₂. There are 2 1's in the binary representation so its binary cardinality is 2.
Given an array of decimal integers, sort it ascending first by binary cardinality, then by decimal value. Return the resulting array.
Function Description
Complete the function cardinalitySort in the editor.
cardinalitySort has the following parameter(s):
int nums[n]: an array of decimal integers
Returns
int[n]: the integer array nums sorted first by ascending binary cardinality, then by decimal value
1Example 1
Input
nums = [31, 15, 7, 3, 2]
Output
[2, 3, 7, 15, 31]
Explanation
31₁₀ → 11111₂ so its binary cardinality is 5.
15₁₀ → 1111₂ so its binary cardinality is 4.
7₁₀ → 111₂ so its binary cardinality is 3.
3₁₀ → 11₂ so its binary cardinality is 2.
2₁₀ → 10₂ so its binary cardinality is 1.
2Example 2
Input
nums = [1, 2, 3, 4, 5]
Output
[1, 2, 4, 3, 5]
Explanation
The sorted elements with binary cardinality of 1 are [1, 2, 4]. The array to return is [1, 2, 4, 3, 5].
3Example 3
Input
nums = [3]
Output
[3]
Explanation
Not privided for now.
4Example 4
Input
nums = [1, 2, 3, 4, 5]
Output
[1, 2, 4, 3, 5]
Explanation
Not privided for now.
Constraints
Limits and guarantees your solution can rely on.
1 ≤ n ≤ 10⁵1 ≤ nums[i] ≤ 10⁶