# Arrange given numbers to form the biggest number | Set 1

Given an array of numbers, arrange them in a way that yields the largest value. For example, if the given numbers are {54, 546, 548, 60}, the arrangement 6054854654 gives the largest value. And if the given numbers are {1, 34, 3, 98, 9, 76, 45, 4}, then the arrangement 998764543431 gives the largest value.

A simple solution that comes to our mind is to sort all numbers in descending order, but simply sorting doesn’t work. For example, 548 is greater than 60, but in output 60 comes before 548. As a second example, 98 is greater than 9, but 9 comes before 98 in output.

So how do we go about it? The idea is to use any comparison based sorting algorithm. In the used sorting algorithm, instead of using the default comparison, write a comparison function myCompare() and use it to sort numbers. Given two numbers X and Y, how should myCompare() decide which number to put first – we compare two numbers XY (Y appended at the end of X) and YX (X appended at the end of Y). If XY is larger, then X should come before Y in output, else Y should come before. For example, let X and Y be 542 and 60. To compare X and Y, we compare 54260 and 60542. Since 60542 is greater than 54260, we put Y first.

Following is the implementation of the above approach. To keep the code simple, numbers are considered as strings, and vector is used instead of normal array.

## C++

 `// Given an array of numbers, program to arrange the numbers to form the ` `// largest number ` `#include ` `#include ` `#include ` `#include ` `using` `namespace` `std; ` ` `  `// A comparison function which is used by sort() in printLargest() ` `int` `myCompare(string X, string Y) ` `{ ` `    ``// first append Y at the end of X ` `    ``string XY = X.append(Y); ` ` `  `    ``// then append X at the end of Y ` `    ``string YX = Y.append(X); ` ` `  `    ``// Now see which of the two formed numbers is greater ` `    ``return` `XY.compare(YX) > 0 ? 1: 0; ` `} ` ` `  `// The main function that prints the arrangement with the largest value. ` `// The function accepts a vector of strings ` `void` `printLargest(vector arr) ` `{ ` `    ``// Sort the numbers using library sort funtion. The function uses ` `    ``// our comparison function myCompare() to compare two strings. ` `    ``// See http://www.cplusplus.com/reference/algorithm/sort/ for details ` `    ``sort(arr.begin(), arr.end(), myCompare); ` ` `  `    ``for` `(``int` `i=0; i < arr.size() ; i++ ) ` `        ``cout << arr[i]; ` `} ` ` `  `// driver program to test above functions ` `int` `main() ` `{ ` `    ``vector arr; ` ` `  `    ``//output should be 6054854654 ` `    ``arr.push_back(``"54"``); ` `    ``arr.push_back(``"546"``); ` `    ``arr.push_back(``"548"``); ` `    ``arr.push_back(``"60"``); ` `    ``printLargest(arr); ` ` `  `    ``// output should be 777776 ` `    ``/*arr.push_back("7"); ` `    ``arr.push_back("776"); ` `    ``arr.push_back("7"); ` `    ``arr.push_back("7");*/` ` `  `    ``//output should be 998764543431 ` `    ``/*arr.push_back("1"); ` `    ``arr.push_back("34"); ` `    ``arr.push_back("3"); ` `    ``arr.push_back("98"); ` `    ``arr.push_back("9"); ` `    ``arr.push_back("76"); ` `    ``arr.push_back("45"); ` `    ``arr.push_back("4"); ` `    ``*/` ` `  `   ``return` `0; ` `} `

## Java

 `// Given an array of numbers, program to ` `// arrange the numbers to form the  ` `// largest number ` `import` `java.util.*; ` ` `  `class` `GFG { ` ` `  `    ``// The main function that prints the  ` `    ``// arrangement with the largest value. ` `    ``// The function accepts a vector of strings     ` `    ``static` `void` `printLargest(Vector arr){ ` `     `  `        ``Collections.sort(arr, ``new` `Comparator(){ ` ` `  `        ``// A comparison function which is used by  ` `        ``// sort() in printLargest() ` `        ``@Override` `        ``public` `int` `compare(String X, String Y) { ` `         `  `        ``// first append Y at the end of X ` `        ``String XY=X + Y; ` `         `  `        ``// then append X at the end of Y ` `        ``String YX=Y + X; ` `         `  `        ``// Now see which of the two formed numbers  ` `        ``// is greater ` `        ``return` `XY.compareTo(YX) > ``0` `? -``1``:``1``; ` `    ``} ` `    ``}); ` `         `  `    ``Iterator it = arr.iterator(); ` ` `  `    ``while``(it.hasNext()) ` `        ``System.out.print(it.next()); ` `     `  `    ``} ` `     `  `    ``// driver program ` `    ``public` `static` `void` `main (String[] args) { ` `         `  `        ``Vector arr; ` `        ``arr = ``new` `Vector<>(); ` `         `  `        ``//output should be 6054854654 ` `        ``arr.add(``"54"``); ` `        ``arr.add(``"546"``); ` `        ``arr.add(``"548"``); ` `        ``arr.add(``"60"``); ` `        ``printLargest(arr); ` `        `  `        ``// output should be 777776 ` `        ``/* arr.add("7"); ` `        ``arr.add("776"); ` `        ``arr.add("7"); ` `        ``arr.add("7"); ` `        ``*/` `         `  `        ``//output should be 998764543431 ` `        ``/*arr.add("1"); ` `        ``arr.add("34"); ` `        ``arr.add("3"); ` `        ``arr.add("98"); ` `        ``arr.add("9"); ` `        ``arr.add("76"); ` `        ``arr.add("45"); ` `        ``arr.add("4"); ` `        ``*/` `    ``} ` `} ` `// This code is contributed by Shubham Juneja `

## Python3

 `# Python3 Program to get the maximum ` `# possible integer from given array ` `# of integers... ` ` `  ` `  `# custom comparator to sort according ` `# to the ab, ba as mentioned in description ` `def` `comparator(a, b): ` `    ``ab ``=` `str``(a) ``+` `str``(b) ` `    ``ba ``=` `str``(b) ``+` `str``(a) ` `    ``return` `((``int``(ba) > ``int``(ab)) ``-` `(``int``(ba) < ``int``(ab))) ` `     `  `def` `myCompare(mycmp): ` `     `  `    ``# Convert a cmp= function into a key= function ` `    ``class` `K(``object``): ` `        ``def` `__init__(``self``, obj, ``*``args): ` `            ``self``.obj ``=` `obj ` `        ``def` `__lt__(``self``, other): ` `            ``return` `mycmp(``self``.obj, other.obj) < ``0` `        ``def` `__gt__(``self``, other): ` `            ``return` `mycmp(``self``.obj, other.obj) > ``0` `        ``def` `__eq__(``self``, other): ` `            ``return` `mycmp(``self``.obj, other.obj) ``=``=` `0` `        ``def` `__le__(``self``, other): ` `            ``return` `mycmp(``self``.obj, other.obj) <``=` `0` `        ``def` `__ge__(``self``, other): ` `            ``return` `mycmp(``self``.obj, other.obj) >``=` `0` `        ``def` `__ne__(``self``, other): ` `            ``return` `mycmp(``self``.obj, other.obj) !``=` `0` `    ``return` `K ` `# driver code ` `if` `__name__ ``=``=` `"__main__"``: ` `    ``a ``=` `[``54``, ``546``, ``548``, ``60``, ] ` `    ``sorted_array ``=` `sorted``(a, key``=``myCompare(comparator)) ` `    ``number ``=` `"".join([``str``(i) ``for` `i ``in` `sorted_array]) ` `    ``print``(number) ` ` `  `# This code is Contributed by SaurabhTewary `

## C#

 `using` `System.Collections.Generic; ` `using` `System; ` ` `  `namespace` `LargestNumberClass ` `{ ` `    ``class` `LargestNumberClass ` `    ``{ ` `        ``//Given a list of non-negative integers,  ` `        ``//arrange them such that they form the largest number. ` `        ``//Note: The result may be very large, so you need to  ` `        ``//return a string instead of an integer. ` ` `  `        ``public` `static` `void` `LargestNumberMethod(List<``int``> inputList) ` `        ``{ ` `            ``string` `output = ``string``.Empty; ` ` `  `            ``List<``string``> newList = inputList.ConvertAll<``string``> ` `            ``(``delegate` `(``int` `i) { ``return` `i.ToString(); }); ` ` `  `            ``newList.Sort(MyCompare); ` ` `  `            ``for` `(``int` `i = 0; i < inputList.Count; i++) ` `            ``{ ` `                ``output = output + newList[i]; ` `            ``} ` ` `  `            ``if` `(output[0] == ``'0'` `&& output.Length > 1) ` `            ``{ ` `                ``Console.Write(``"0"``); ` `            ``} ` `            ``Console.Write(output); ` `        ``} ` ` `  `        ``internal` `static` `int` `MyCompare(``string` `X, ``string` `Y) ` `        ``{ ` `            ``// first append Y at the end of X  ` `            ``string` `XY = X + Y; ` ` `  `            ``// then append X at the end of Y  ` `            ``string` `YX = Y + X; ` ` `  `            ``// Now see which of the two formed numbers is greater  ` `            ``return` `XY.CompareTo(YX) > 0 ? -1 : 1; ` `        ``} ` `    ``} ` ` `  `    ``class` `Program ` `    ``{ ` `        ``static` `void` `Main(``string``[] args) ` `        ``{ ` `            ``List<``int``> inputList = ``new` `List<``int``>() { 54, 546, 548, 60 }; ` `            ``LargestNumberClass.LargestNumberMethod(inputList); ` `        ``} ` `    ``} ` `} `

## PHP

 ` 0 ? 1: 0;  ` `}  ` ` `  `// The main function that prints the ` `// arrangement with the largest value.  ` `// The function accepts a vector of strings  ` `function` `printLargest(``\$arr``)  ` `{  ` `    ``// Sort the numbers using library sort  ` `    ``// function. The function uses our  ` `    ``// comparison function myCompare() to  ` `    ``// compare two strings.  ` `    ``// See http://www.cplusplus.com/reference/algorithm/sort/  ` `    ``// for details  ` `    ``usort(``\$arr``, ``"myCompare"``);  ` ` `  `    ``for` `(``\$i` `= 0; ``\$i` `< ``count``(``\$arr``) ; ``\$i``++ )  ` `        ``echo` `\$arr``[``\$i``];  ` `}  ` ` `  `// Driver Code ` `\$arr` `= ``array``(``"54"``, ``"546"``, ``"548"``, ``"60"``);  ` `printLargest(``\$arr``);  ` ` `  `// This code is contributed by  ` `// rathbhupendra ` `?> `

Output:

`6054854654`

Another approach:(using itertools)

 `# Python3 implementation this is to use itertools. ` `# permutations as coded below: ` ` `  `from` `itertools ``import` `permutations ` `def` `largest(l): ` `    ``lst ``=` `[] ` `    ``for` `i ``in` `permutations(l, ``len``(l)): ` `        ``# provides all permutations of the list values, ` `        ``# store them in list to find max ` `        ``lst.append("".join(``map``(``str``,i)))  ` `    ``return` `max``(lst) ` ` `  `print``(largest([``54``, ``546``, ``548``, ``60``])) ``#Output 6054854654 ` ` `  `# This code is contributed by Raman Monga `