BinaryCardinality | Topcoder Archive

Problem Statement

The cardinality of a binary number is given as the total number of "ones" it contains. For example, the cardinality of binary 10100 (decimal 20) is 2, because there are 2 "ones". The cardinality of binary 11110 (decimal 30) is 4, because there are 4 "ones".

Given a int[] of decimal numbers arrange them in ascending order of binary cardinality and return this arranged int[]. If two numbers have the same binary cardinality, then the smaller number must come first in the arranged int[].

Definition

Class:: BinaryCardinality
Method:: arrange
Parameters:: int[]
Returns:: int[]
Method signature:: int[] arrange(int[] numbers)
(be sure your method is public)

Constraints

numbers will have between 1 and 50 elements inclusive.
each element of numbers will be between 0 and 1000000 inclusive.

Examples

```
{4}
```
```
Returns: { 4 }
```
There is only one element in the array, so it must be returned.
```
{31,15,7,3,2}
```
```
Returns: { 2,  3,  7,  15,  31 }
```
We start by converting the above set of decimals into binary numbers. We get the following array: {11111, 1111, 111, 11, 10}. Now we can calculate the cardinality of each number: {5, 4, 3, 2, 1}. So 2 has the lowest binary cardinality, followed by 3, 7, 15 and finally 31.
```
{10,9,8,7,6,5,4,3,2,1}
```
```
Returns: { 1,  2,  4,  8,  3,  5,  6,  9,  10,  7 }
```
The cardinality array is {2, 2, 1, 3, 2, 2, 1, 2, 1, 1}. Note that although 10 and 3 have the same cardinality of 2, 3 must come earlier because it is smaller in value.

{811385,340578,980086,545001,774872,855585,13848,863414,419523,190151,784903,127461}

Returns: { 13848,  340578,  545001,  855585,  419523,  811385,  127461,  190151,  774872,  863414,  784903,  980086 }

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.