Last Updated: 26 Aug, 2020
Rearrange Array Numbers to form Largest Possible Number
Moderate
Asked in companies
You are given an array(ARR) of length 'N', consisting of non-negative integers. Using only these given numbers, rearrange the numbers in such a way that the resultant number thus formed is the largest possible. You cannot change the order of digits of a number.
For Example:
Given array numbers 12, 5, 34, the largest number you can form with them is 53412. There are other possible arrangements like 51234 or 34125, but they are both less than 53412.
Note:
As the final number formed after concatenation can be very large, print it as a string.
Input Format:
The first line of input contains a single integer 'T', representing the number of test cases or queries to be run.
Then the test cases follow.
For each test case, the first input line contains a single integer 'N', the size of the array.
The second line contains 'N' single space-separated integers representing the elements in the array.
Output Format:
For each test case, print a single line containing a single integer denoting the largest possible number that can be formed using the given array numbers.
The output for every test case will be printed in a separate line.
Note:
You are not required to print anything explicitly. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 100
1 <= N <= 10 ^ 3
0 <= ARR[i] <= 10 ^ 3
Where 'T' is the number of test cases, 'N' is the size of the array and 'ARR[i]' represents the integers present in the array.
Time limit: 1 sec.
Approaches
We can divide this problem into non-overlapping sub-problems, and simply merge the results of the smaller sub-problems to obtain the result for the larger ones. Let’s see how:
Consider the task of sorting the array in such a way, that when we go from index 1 to N, and concatenate numbers in order, we obtain the largest possible number. How do we decide which number comes first? We create a custom comparator for that, details of which will be discussed further below.
We can divide this problem into two halves: 1) Sorting the array [1, N/2], and 2) Sorting the array [N/2+1, N]. As you can observe, we are, in essence, applying merge sort. You can use any sorting technique here, but a merge sort is quite optimal, and intuitive in this case as well.
However, our algorithm differs when merging two sub-problems. Let the two numbers that we obtain as results are X and Y (X and Y are maximum possible). There are two ways of merging these two numbers: 1) X+Y and 2) Y+X. So we simply check which of these combinations is larger. How do we do that?
As we are working with strings (we convert these numbers to strings first), and the lengths of their combinations are equal, the lexicographically larger string will be the larger number. We create a custom comparator following this comparison criteria. The concatenation of all numbers in the sorted array will be our answer.
Similar problems