Form the Largest Number
- 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.
Arranging an array in a particular order should trigger the idea to implement our custom sorting strategy.
In Java, it means implementing the
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: 1 and 1
Lexicographically 11 <= 11, output is 1 then 1Inputs: 25 and 27
Lexicographically 2527 < 2725, output is 27 then 25Inputs: 3 and 30
Lexicographically 303 < 330, output is 3 then 30Inputs: 12 and 121
Lexicographically 12112 < 12121, output is 12 then 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.