Sort by Digit Difference
MediumPractice library · +20 XPsortingcustom sortingsorting then scanning
Given N integers, sort them based on the absolute difference between their largest and smallest digit. If two numbers have the same digit difference, sort them in ascending order. Print the sorted sequence.
Input
The first line contains an integer N (1 <= N <= 200000). The second line contains N space-separated integers, a_1, a_2, ..., a_N (-10^9 <= a_i <= 10^9).
Output
Print the N integers in the sorted order, separated by spaces.
Constraints
1 <= N <= 200000, -10^9 <= a_i <= 10^9
Time limit 2 s (native code; slower languages get more)Memory 256 MB14 hidden tests
Example 1
Input
5 123 45 90 111 607
Output
111 45 123 607 90
Differences: 123->2, 45->1, 90->9, 111->0, 607->1. Sorted by diff: 111(0), 45(1), 607(1), 123(2), 90(9). Tie-break 45 and 607 by value: 45 comes before 607.
Example 2
Input
3 -10 20 5
Output
5 -10 20
Differences: -10->1 (abs(-10)=10, diff 1-0=1), 20->2 (diff 2-0=2), 5->0 (diff 5-5=0). Sorted: 5(0), -10(1), 20(2).
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 123 45 90 111 607
Example 2 input
3 -10 20 5