BinaryCardinality
SRM 166 · 2003-10-01 · by dimkadimon
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
Constraints
- numbers will have between 1 and 50 elements inclusive.
- each element of numbers will be between 0 and 1000000 inclusive.
{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.
{242665,654565,143441,941046,352005,556430,428364,221286,598429,97864,972766,99749,5045,704958,131265,733803,436797,27896,384433,882598,381060,165343,744979,348723,394629,829451,950411,350802,515108,632563,969170,303503,431771,369058,547436,1951,364290,764409,880267,134257,407296,668402}
Returns: { 131265, 143441, 134257, 381060, 394629, 407296, 5045, 99749, 221286, 364290, 369058, 428364, 829451, 950411, 1951, 27896, 97864, 303503, 348723, 350802, 547436, 598429, 352005, 515108, 668402, 165343, 431771, 436797, 556430, 704958, 733803, 744979, 969170, 242665, 384433, 632563, 880267, 654565, 764409, 882598, 941046, 972766 }
{361803,721474,597615,568278,134243,388294,981360,470193,188405,9666,84284,603282,655586,900130,166986,129229,906615,609697,695144,92039,582043,807275,595499,53474,972222,617742,505609,109347,379979,614008,547048,920130,619151,818698,750401,745760,728923,879675,765242,987266,317004,49439,899456,406713,683861,720516,849615}
Returns: { 9666, 655586, 721474, 53474, 134243, 166986, 745760, 920130, 987266, 49439, 84284, 547048, 603282, 109347, 317004, 361803, 595499, 609697, 899456, 92039, 379979, 406713, 470193, 582043, 617742, 695144, 750401, 807275, 818698, 900130, 129229, 388294, 505609, 568278, 614008, 619151, 720516, 597615, 683861, 765242, 879675, 981360, 728923, 188405, 849615, 906615, 972222 }
Submissions are judged against all 38 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BinaryCardinality with a public method vector<int> arrange(vector<int> numbers) · 38 test cases · 2 s / 256 MB per case