Form the Biggest Number
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

Question

Form the Biggest Number

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

Accepted Answer

Using the inbuilt library of Python, itertools library can be used to perform this task.

Accepted Answer

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.

Space Complexity: OtherExplanation:

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)).

Time Complexity: OtherExplanation:

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)).

Accepted Answer

Sorting

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.

Space Complexity: OtherExplanation:

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, N * log10(MAX) will be the space required to store the N auxiliary array elements. So the overall space complexity is O(N * log10(MAX)).

Time Complexity: OtherExplanation:

O(N * log(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, it takes O(N * log(N)) to sort an array of N elements and it takes log10(MAX) to compare two elements of the auxiliary array. Hence, the overall time complexity is O(N * log(N) * log10(MAX)).

Accepted Answer

Custom Sort Method

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.

Space Complexity: OtherExplanation:

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. So the overall space complexity is O(N * log10(MAX)).

Time Complexity: OtherExplanation:

O(N * log(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, it takes O(N * log(N)) to sort an array of N elements and it takes log10(MAX) to compare two elements using the comparator function. Hence, the overall time complexity is O(N * log(N) * log10(MAX)).

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:

Input format:

Output format:

Note:

Constraints:

Top Tata 1mg Software Developer interview questions & answers

Popular interview questions of Software Developer