SumSort
TCI '02 Semifinals 2 · 2002-11-22 · by brett1479
TCI '02 Semifinals 2 · 2002-11-22 · by brett1479 · Advanced Math, Search, Sorting
Problem Statement
Problem Statement
Given an inclusive range of numbers you will first sort them in ascending order by their digit sum
(sum of their decimal digits). Ties are settled by the numbers' values, lower numbers first. You
will then return the value at location pos (0-based) in the newly sorted list. For example:
rangeLow = 0
rangeHigh = 10
pos = 3
The sorted range is : 0,1,10,2,3,4,5,6,7,8,9. The value at position 3 is 2. Note that 10 comes before 2 since the digit sum of 10 is 1 whereas the digit sum of 2 is 2. Also note that 10 comes after 1 even though they have the same digit sum since 10 is greater than 1.
rangeLow = 0
rangeHigh = 10
pos = 3
The sorted range is : 0,1,10,2,3,4,5,6,7,8,9. The value at position 3 is 2. Note that 10 comes before 2 since the digit sum of 10 is 1 whereas the digit sum of 2 is 2. Also note that 10 comes after 1 even though they have the same digit sum since 10 is greater than 1.
Constraints
- rangeLow will be between 0 and 1000000000 (10^9) inclusive
- rangeHigh will be between 0 and 1000000000 (10^9) inclusive
- rangeLow will be less than or equal to rangeHigh
- pos will be between 0 and (rangeHigh - rangeLow) inclusive
Examples
0)
0 1000000000 1000000 Returns: 102721002
1)
0 10 4 Returns: 3
2)
100 200 5 Returns: 111
3)
0 1000000000 40 Returns: 10000010
4)
0 1000000000 999940000 Returns: 987996896
56)
0 10 3 Returns: 2
This is the example above
57)
78 93 13 Returns: 79
The numbers are sorted as: 80, 81, 90, 82, 91, 83, 92, 84, 93, 85, 86, 78, 87, 79, 88, 89
Submissions are judged against all 59 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class SumSort with a public method int valueAt(int rangeLow, int rangeHigh, int pos) · 59 test cases · 2 s / 256 MB per case