# Form the Largest Number

# Problem

- Largest number: InterviewBit

Given a list of non negative integers, arrange them such that they form the largest number.Example:

Given [3, 30, 34, 5, 9], the largest formed number is 9534330. The result may be very large, so you need to return a string instead of an integer.

Category: Arrays

# Solving Process

Arranging an array in a particular order should trigger the idea to implement our custom sorting strategy.

In Java, it means implementing the `Comparable`

interface.

As such, this problem is not very complex but it might be easy to make a mistake during the sorting strategy implementation.

Let’s see some examples of the desired outputs of our sorting implementation, considering we would like to sort them in the reverse order (9 < 8 means we will produce the output 98):

`Inputs: 1 and 1, output: 1 then 1`

Inputs: 25 and 27, output: 27 then 25

Inputs: 3 and 30, output: 3 then 30

Inputs: 12 and 121, output: 12 then 121

There’s a little trick here, hopefully, you spotted it.

The easiest solution is to concatenate (not adding, concatenate) the two integers in both ways and to compare them:

For clarity, the first input is in bold.Inputs:1and 1

Lexicographically11 <= 11, output is1then 1Inputs:25and 27

Lexicographically2527 < 2725, output is 27 then25Inputs:3and 30

Lexicographically 303<330, output is3then 30Inputs:12and 121

Lexicographically 12112<12121, output is12then 121

A possible implementation in Java:

To return a valid integer representation, we just have to make sure the input `0 0 0 0`

return `0`

and not `0000`

. This is done by checking if the first element of the `containers`

array is equals to 0.

The time complexity is O(n log(n)) with `n`

the number of elements of the list as we have to sort the array. The space complexity is O(n) (linear), with `n`

representing also the number of elements, as we have to create another array to implement the sorting strategy.