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

Download   Run Code

Output:

99768211210

C++

Download   Run Code

Output:

99768211210

Java

Download   Run Code

Output:

99768211210

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

 
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

avatar
  Subscribe  
newest oldest most voted
Notify of
steve
Guest

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

Karan
Guest

C++ version for the code :

Ankita
Guest

Nice

Muhammad Amir Pervaiz
Guest
Muhammad Amir Pervaiz

Swift version 🙂
var numbers = [10,68,75, 7,21,12]
numbers = numbers.sorted { (x, y) -> Bool in

let str1 = “\(x)\(y)”
let str2 = “\(y)\(x)”
let num1 = str1
let num2 = str2
return num1 > num2
}
print(numbers)

Guest
Guest

What’s is the reason to choose qsort over sort?