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.

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 –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
#include <stdio.h> #include <string.h> #include <stdlib.h> /* Note - An element of arr is of type char*, and the const void* in compare point to *char, so what is actually being passed is a char**. Therefore, proper cast is *(const char**)a */ int compare(const void *a, const void *b) { const char **X = (const char **)a; const char **Y = (const char **)b; int len = strlen(*X) + strlen(*Y) + 1; // create a new string X + Y char XY[len]; strcpy(XY, *X); strcat(XY, *Y); // create a new string Y + X char YX[len]; strcpy(YX, *Y); strcat(YX, *X); // larger of YX and XY should come first in sorted array return strcmp(YX, XY); } // main function int main() { char *arr[] = { "10", "68", "75", "7", "21", "12" }; int n = sizeof(arr)/sizeof(arr[0]); // custom sort qsort(arr, n, sizeof(arr[0]), compare); // print the sorted sequence for (int i = 0; i < n ; i++ ) printf("%s", arr[i]); return 0; } |

**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

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