Last Updated: 31 Dec, 2020
Form the Biggest Number
Moderate
Asked in companies
Given an array “A” of positive integers. Your task is to make the largest number possible formed by concatenating each of the array elements exactly once.
Example:
Let's say the given array is [ 9, 98, 7].
All the possible numbers formed by concatenating each of the array elements are 7989,7998,9879,9897,9987,9798. Among the six numbers, 9987 is the greatest number. Hence the answer is 9987.
Input format:
The first line of input contains an integer ‘T’ denoting the number of test cases.
Then the T test cases follow.
The first line of each test case contains an integer 'N' denoting the number of elements in the array.
The second line of each test case contains 'N' space-separated integers denoting the array elements.
Output format:
For each test case, print the largest number possible formed by concatenating each of the array elements exactly once.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1<= T <=10
1<= N <=10^3
0<= A[i] <=10^9
Time Limit: 1sec
Approaches
The idea is to try out all the possible answers one by one and find out the largest one among all of them.
To implement this approach, we will generate all the permutations of the first 'N' positive integers and concatenate all the array elements in the order of the permutation.
For e.g. N=3 and array A = [ 3, 34, 7 ].
Let's generate all the possible answers using the permutations. Let "a=> b" denote the concatenation of integer a with b.
- A[1] => A[2] => A[3] = 3347
- A[1] => A[3] => A[2] = 3734
- A[2] => A[1] => A[3] = 3437
- A[2] => A[3] => A[1] = 3473
- A[3] => A[1] => A[2] = 7334
- A[3] => A[2] => A[1] = 7343
As we can see the largest number among the above is 7343. Hence, 7343 will be our answer.
Steps:
- Initialize an empty string say ans.
- Generate all permutations of an array.
- For each permutation check the number that can be obtained by concatenating A[1] => A[2] …..=> A[N]. is greater than ans or not. If yes then update the ans with the current number obtained from the current permutation.
- At last, return ans.
The idea is to build an auxiliary array in which all the array elements should have the same number of digits so that we can simply sort the auxiliary array in descending order and concatenate the array elements in that particular order to form the largest number possible.
The process required to build the auxiliary array is explained below:
- Find the array elements having the maximum number of digits. Let”s denote the maximum number of digits by K.
- For every element in the array, let’s denote the number of digits in it by P.
- The corresponding auxiliary element will contain the array element concatenated (K/P) times followed by the first (K%P) digits of the array element.
See the image for a better understanding
After building the auxiliary array we will sort it in descending order then concatenate all the corresponding array elements in the order of the auxiliary elements to form the greatest number possible.
To solve this problem is to sort the array in descending order, but the sorting list/array does not work here. For example, 213 is greater than 75 but in a sorted array, 75 comes after 213. And this would produce the number 21375. But the largest number that can be formed is 75213. therefore sorting will not work here. But we can modify the comparator function of sort().
The idea is to use any of the comparison-based sorting algorithm
- We will write our own custom comparator function for sorting.
- For the two numbers A and B. This custom function will not compare the A and B with each other. But it compares AB with BA and the greater number will come first in sorted order.
- Here AB means the number is formed by appending A to B vice versa for BA.
For Example A = 213 and B = 75 then AB = 21375 and BA = 75213.To compare A and B our custom compare function will compare AB and BA, Since AB < BA so, we will put B first in sorted list/array.
Similar problems