FastPrep
Problem · Sorting

Cardinality Sorting

Learn this problem
● EasyOracleFULLTIMEOA

Problem statement

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

cardinalitySort(nums: int[]) → int[]

Complete the function cardinalitySort in the editor.

cardinalitySort has the following parameter(s):

  1. 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

Examples

Example 1

nums = [31, 15, 7, 3, 2]return = [2, 3, 7, 15, 31]
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.

Example 2

nums = [1, 2, 3, 4, 5]return = [1, 2, 4, 3, 5]
The sorted elements with binary cardinality of 1 are [1, 2, 4]. The array to return is [1, 2, 4, 3, 5].

Example 3

nums = [3]return = [3]
Not privided for now.

Example 4

nums = [1, 2, 3, 4, 5]return = [1, 2, 4, 3, 5]
Not privided for now.

Constraints

  • 1 ≤ n ≤ 10⁵
  • 1 ≤ nums[i] ≤ 10⁶

More Oracle problems

drafts saved locally
public int[] cardinalitySort(int[] nums) {
    // write your code here
}
nums[31, 15, 7, 3, 2]
expected[2, 3, 7, 15, 31]
checking account