Form the Biggest Number

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
11 upvotes
Asked in companies
BarclaysArcesiumIntuit

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
3
22 224 139
2
15 9
Sample Output 1:
22422139
915
Explanation For Sample Input 1:
For the first test case, the six possible answers are:
[22422139, 22413922, 13922224, 13922422, 22224139, 22139224] 

Among them 22422139 is the greatest number. Hence, our answer is 22422139.

For the second test case, there are only two possible answers 159 and 915. Among both , 915 is bigger. Hence, our answer is 915.
Sample Input 2:
2 
4
999 989 123 9
3
88 883 889
Sample Output 2:
9999989123
88988883
Hint

Generate all the possible answers and find the largest among them.

Approaches (3)
Brute Force approach

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.
Time Complexity

O(N! * N * log10(MAX)), where ‘N’ is the number of elements in the array and MAX is the maximum among the array elements.

 

In the worst case, we will generate all the N! Permutations and for each permutation, we will be iterating the array elements once and it takes log10 (MAX) iterations for a single array element. So the overall time complexity is O(N! * N * log10 (MAX)).

Space Complexity

O(N * log10(MAX)), where ‘N’ is the number of elements in the array and MAX is the maximum among the array elements.

 

In the worst case, we need to store only the maximum possible answer among all the answers. So the overall space complexity is O(N * log10(MAX)).

Code Solution
(100% EXP penalty)
Form the Biggest Number
Full screen
Console