Rearrange Array Numbers to form Largest Possible Number

Moderate
0/80
Average time to solve is 35m
profile
Contributed by
8 upvotes
Asked in companies
AmazonMicrosoftAmdocs

Problem statement

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.

arr

Note: 
As the final number formed after concatenation can be very large, print it as a string.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
2
5
1 20 300 4 50
3
98 987 986
Sample Output 1:
504300201
98987986
Explanation for Sample Input 1:
In the first test, if we arrange the number as 50, 4, 300, 20, 1, we get 504300201.

In the second test, if we arrange the numbers as 98, 987, 986, we get 98987986.
Sample Input 2:
1
2
90 9
5 
5 4 3 2 10
Sample Output 2:
990
543210
Hint

First off, observe that a seemingly obvious approach of concatenating numbers in descending order won’t work (For numbers 78 and 9, 978 is larger than 789). Now, assume you only have two numbers. There are only two ways of concatenating them, so you try out both, and return the greater number. Whenever you ‘merge’ two numbers, you want to ensure that both numbers that you are merging are the maximum possible. Can you now think of a ‘Divide & Conquer’ strategy to solve this? 

Approaches (1)
Sorting With Custom Comparator

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.

Time Complexity

O(N * A * log(N)), ‘N’ is the size of the array, and ‘A’ represents the number of digits in the array integers.

 

If we draw a recursion tree of the whole process, we observe that each level of the tree takes O(N * A) time, and there are O(log(N)) levels. Hence, the total time complexity per test case is O(N * A * log(N)).

Space Complexity

O(N * A), where ‘N’ is the size of the array, and ‘A’ represents the number of digits in the array integers.

 

The final string obtained will be of size O(N * A).

Code Solution
(100% EXP penalty)
Rearrange Array Numbers to form Largest Possible Number
Full screen
Console