Largest Number Formed From Array

Given an array of non-negative integers, arrange the elements so that when they are concatenated together (as decimal strings, in some order) they form the single largest possible number. Return that number as a string, with no leading zeros unless the result itself is zero.

Input: The first line contains an integer n. The second line contains n space-separated non-negative integers. Output: Print a single line containing the largest number (as a string) that can be formed by concatenating the array elements in some order.

1 <= n <= 8000 0 <= a[i] <= 10^9

The all-zero edge case (every number is 0, so concatenating naively gives '000...0') needs explicit handling to collapse to a single '0' - since leading zeros are disallowed in the final answer except for this exact case.

Arrange a set of numbers so that concatenating them together forms the largest possible combined number. Brute force: Try every possible permutation of the numbers and check which concatenation produces the largest result - this costs O(n! * n) in the worst case, completely impractical beyond a tiny handful of numbers. Optimised: The custom comparator 'compare a+b against b+a as strings' captures EXACTLY the right notion of 'which number should come first to maximize the combined result' - sorting with this comparator (rather than by plain numeric value, which would incorrectly put '3' before '30' by magnitude even though '303' < '330') achieves the true maximum arrangement in standard O(n log n) sorting time.

1. Compare two numbers NOT by their plain numeric value, but as STRINGS: for numbers a and b, decide their relative order by comparing the CONCATENATION (a+b) against (b+a). 2. Sort the array of numbers (treated as strings) using this custom comparator, in DESCENDING order. 3. Concatenate all the sorted strings together; handle the special all-zero case by collapsing the result to a single '0' rather than a string of zeros.

Time: O(n log n * L), where L is the average string length - each comparator call costs O(L) to build and compare the two concatenated strings. Space: O(n * L), for the string representations of all numbers.

All elements could be 0 (the answer must be the single character "0", never a string of multiple zeros), or the array could contain numbers that are prefixes of one another (e.g. 3 and 34).

Be ready to give a concrete counter-example showing why plain numeric or plain lexicographic sorting FAILS here (like 3 vs 30) - demonstrating this failure case is exactly what motivates the custom a+b vs b+a comparator.