Find largest number possible from set of given numbers

Find largest number possible from set of given numbers. The numbers should be appended to each other in any order to form the largest number.

 

For example,


Input:  { 10, 68, 75, 7, 21, 12 }
Output: 77568211210

 


 

Simply sorting the array in descending order and considering the sorted order is not a possibility here as sorted array {75, 68, 21, 12, 10, 7} will result in number 75682112107 which is less than largest number possible 77568211210.

 

The idea is to write our own custom comparator function for the sorting routine. For two numbers X and Y, the custom comparator function will not compare X and Y with each other but it compares XY with YX and the greater number will come first in sorted order. Here, XY denotes number formed by appending Y to X and YX denotes number formed by appending X to Y.

For example, for X = 15 and Y = 4, XY = 154 and YX = 415.

As evident from above example, X > Y but XY < YX, so the comparator function will consider Y > X.

 
C implementation –
 

Download   Run Code

Output:

97568211210

 
The time complexity of above solution is O(nlogn) and auxiliary space used by the program is O(1).

 
Source: Amazon Interview

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
steve
steve

This is a c version of the answer, a c++ version is cpp.sh/7yap

wpDiscuz