Given an array numbers, we have to join them in such a way that it forms the biggest number.
For example consider the simple three element array [10,3,2], they can be joined in following ways
1032, 1023, 2103, 2310, 3102, 3210. Among these numbers 3210 is the biggest number.
To solve this problem we definitely have to sort the given numbers using some criteria to form the biggest number.
Considering the above example, if we simply sort them in descending order, the array becomes [10,3,2] which does not form the biggest number.
Similarly we can also sort numbers by comparing the numbers string comparison. This does not work in cases like [1,10]. Since “10” > “1” the array in sorted as [10,1], but 110 is the biggest number.
We should think of a custom comparison function which guarantees us the biggest number when joined. Let us join the two numbers to be compared in two ways and compare them.
Considering the above example, they become 110 (“1″+”10”), 101( “10”+”1″). Since 110 is higher we place 1 first in sorting order before 10.
Here is the simple python implementation of the above algorithm. Also see my post on geeksforgeeks for C++ implementation of the same algorithm.