Sort by Digit Sum
MediumPractice library · +20 XPsortingdigit sum
Given a list of N positive integers, sort them in ascending order. If two numbers have the same digit sum, they should maintain their relative order from the original list. After sorting, calculate the sum of digit sums of all numbers in the sorted list.
Input
The first line contains an integer N. The second line contains N space-separated positive integers.
Output
A single integer representing the sum of digit sums of all numbers in the sorted list.
Constraints
1 <= N <= 200000; 1 <= a[i] <= 10^9
Time limit 1 s (native code; slower languages get more)Memory 256 MB13 hidden tests
Example 1
Input
5 12 3 45 101 6
Output
23
Digit sums: 3, 3, 9, 2, 6. Sorted by digit sum (stable): 101(2), 12(3), 3(3), 6(6), 45(9). Sum of digit sums: 2+3+3+6+9 = 23.
Example 2
Input
4 9 18 27 36
Output
36
Digit sums: 9, 9, 9, 9. All digit sums are equal, so relative order is preserved. Sum of digit sums: 9+9+9+9 = 36.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
5 12 3 45 101 6
Example 2 input
4 9 18 27 36