A small foundry has just poured a batch of n metal ingots, and every ingot has been assigned an integer purity rating. Before shipment, quality control requires that every ingot in the batch carry the exact same purity rating, and — for this batch's certification mark — that shared rating must be a palindrome, meaning its decimal digits read the same forwards and backwards (0, 7, 22, and 1331 all qualify; 10 and 205 do not). Recasting ingot i from its current rating to a new rating y costs |rating[i] - y| units of alloy, since that is exactly how much material must be added or melted away. The target rating y itself may be any non-negative integer palindrome, whether or not it currently appears on any ingot. Determine the minimum total alloy cost needed to bring every ingot in the batch to one common palindromic rating.
Line 1: a single integer n — the number of ingots. Line 2: n space-separated integers rating[1..n] — the current purity rating of each ingot.
A single integer: the minimum total alloy cost.
Example 1
Input
5 1 2 3 4 5
Expected
6
Explanation
Sorted, the ratings are 1,2,3,4,5 with median 3, which is already a palindrome (a single digit). Recasting every ingot to rating 3 costs |1-3|+|2-3|+|3-3|+|4-3|+|5-3| = 2+1+0+1+2 = 6, and no other palindrome does better, so the minimum alloy cost is 6.
Example 2
Input
4 10 15 20 25
Expected
24
Explanation
Sorted, the ratings are 10,15,20,25; the two middle values are 15 and 20, and any y in that window ties for the unrestricted minimum. Neither 15 nor 20 is a palindrome, so the search checks nearby palindromes such as 11 and 22. Recasting every ingot to 22 costs |10-22|+|15-22|+|20-22|+|25-22| = 12+7+2+3 = 24, which is the minimum achievable over every candidate palindrome.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →