Biggest number from parts
Arrange whole numbers side by side to form the biggest possible number, by sorting them with a custom rule that compares joined pairs. About 18 minutes.
Compare two joined orders
Given 3 and 30, which goes first? Joined as 330 or as 303, the first is bigger, so 3 goes first. Sorting as plain text or by size fails: text order puts 30 before 3 sometimes, and size order cannot tell 9 from 91.
Ask the real question for any two parts a and b: is a followed by b bigger than b followed by a? Whichever is bigger decides who goes first.
Sort and join
Turn each number into text, then sort using that pair rule. Because the rule is consistent, it behaves like a true order, so the sorted list is the best arrangement and joining it gives the answer.
One edge case: if the biggest part is 0, every part is zero, and the answer is just a single 0 rather than 000.
parts = [str(n) for n in nums]
parts.sort(key=cmp_to_key(bigger))
if parts[0] == "0":
return "0"
return "".join(parts)9 first: 9 then 5 is 95, bigger than 59.
Which order is better for 8 and 89?
- A89 then 8, giving 898
- B8 then 89, giving 889
- CThey are equal
Show the answer
89 then 8, giving 898. 898 is bigger than 889.
Biggest joined number
Given a list of non-negative integers nums, arrange them so that joining them side by side forms the biggest possible number. Return that number as a string, since it can be very large.
nums = [3, 30, 34, 5, 9] → "9534330"
1 ≤ nums.length ≤ 1,000 · 0 ≤ nums[i] ≤ 1,000,000,000