# Form the Largest Number Strings, Sorting

Hard

### Problem Statement (Simplified):

Given an array of numbers, arrange them in such a way that they form the largest number on joining.

See original problem statement here

#### Test Case

``````Input:
4
64 646 56 46

Output:
646645646

Explanation:
On joining above elements in different order and combinations, we get total 24 numbers :

646465646
646645646
566464646
645664646
646566446
566466446
566464664
646564664
465664664
564664664
646465664
466465664
466456646
644656646
564664646
465664646
645646646
566446646
646644656
646464656
466466456
646466456
644664656
466464656

In all combinations, we can see 646645646 is the largest number, so 646645646 is our answer.``````

### Solving Approach :

#### Bruteforce Approach:

1) We can check all the permutations of all the elements in the array.
2) For all the permutation, we’ll convert them into numbers and then check which of them is maximum and after checking all permutations we print the maximum number.
3) All permutations of the array take `O(N!)` which is very inefficient. So we move to another approach which is more efficient than this.

#### Efficient Approach :

1) The efficient approach uses String comparison and sorting.
2) We sort the array by using a custom comparing function.
3) When comparing two strings, let’s say `A` and `B`, we concatenate them in the form of `AB` and `BA`.
4) Then we check which one of them is big, if `BA` is greater than `AB`, then we swap both and move forward.
5) After sorting is done, we print all the numbers in sequence. This results in the required number.

#### Example

Let’s take test case we discussed above, where array a is `[64,646,56,46]`.
We can dry run for above procedure as :

For i = 0:

• j = 1 :

Value at `a[i]` is `64` and value at `a[j]` is `646`.
On cocatenating them, we get `AB = 64646` and `BA = 64664`.
As we can see value of `BA` is greater than value of `AB`, so we swap both values, and array becomes `[646,64,56,46]`.

• j = 2 :

Value at `a[i]` is `646` and value at `a[j]` is `56`.
On cocatenating them, we get `AB = 64656` and `BA = 56646`.
As we can see value of `BA` is smaller than value of `AB`, so we keep the array same.

• j = 3 :

Value at `a[i]` is `646` and value at `a[j]` is `46`.
On cocatenating them, we get `AB = 64646` and `BA = 46646`.
As we can see value of `BA` is smaller than value of `AB`, so we keep the array same.

For i = 1:

• j = 2 :

Value at `a[i]` is `64` and value at `a[j]` is `56`.
On cocatenating them, we get `AB = 6456` and `BA = 5664`.
As we can see value of `BA` is smaller than value of `AB`, so we keep the array same.

• j = 3 :

Value at `a[i]` is `64` and value at `a[j]` is `46`.
On cocatenating them, we get `AB = 6446` and `BA = 4664`.
As we can see value of `BA` is smaller than value of `AB`, so we keep the array same.

For i = 2:

• j = 3 :

Value at `a[i]` is `56` and value at `a[j]` is `46`.
As we can see value of `BA` is smaller than value of `AB`, so we keep the array same.

As we can see whole array is sorted accordigly as we wanted, so final array is `[646,64,56,46]`. So, we print whole array with no gap as our answer. `646645646` is our answer.

### Solutions

```#include <stdio.h>
#include<string.h>

void swap( char *first, char *second){

char AB, BA;
strcpy(AB, first);
strcpy(BA, second);

strcat(AB,second);
strcat(BA,first);

if(strcmp(BA,AB)>0){
char temp;
strcpy(temp,second);
strcpy(second,first);
strcpy(first,temp);
}

}

int main()
{
int test;
scanf("%d",&test);

while(test--){

int n;
scanf("%d", &n);

char a[n];
for(int i=0; i<n; i++){
scanf("%s", a[i]);
}

for(int i=0; i<n; i++)
for(int j=i+1; j<n; j++)
swap(a[i],a[j]);

for(int i=0; i<n; i++)
printf("%s",a[i]);

printf("\n");
}
}
```
```#include <bits/stdc++.h>
using namespace std;
int myCompare(string A, string B)
{
string AB = A.append(B);
string BA = B.append(A);
return AB.compare(BA) > 0 ? 1: 0;
}

int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
vector<string> arr(n);
for(int i=0;i<n;i++)
{
cin >> arr[i];
}
sort(arr.begin(), arr.end(), myCompare);
for (int i=0; i < arr.size() ; i++ )
cout << arr[i];
cout<<"\n";
}
}
```
```import java.util.*;

class prepBytes {

static void printLargestVal(Vector<String> arr){

Collections.sort(arr, new Comparator<String>(){
@Override
public int compare(String X, String Y) {

String XY=X + Y;
String YX=Y + X;

return XY.compareTo(YX) > 0 ? -1:1;
}
});

Iterator it = arr.iterator();

while(it.hasNext())
System.out.print(it.next());
System.out.println();

}

public static void main (String[] args) {

Scanner sc= new Scanner(System.in);
int test_cases;
test_cases = sc.nextInt();

while(test_cases != 0){

int n;
n = sc.nextInt();
Vector<String> arr;
arr = new Vector<>();

for(int i=0; i<n ; i++){
int temp = sc.nextInt();
}
printLargestVal(arr);

test_cases--;
}
}
}
```
```for _ in range(int(input())):

n = int(input())
arr = input().split()
arr.sort(reverse = True)
print(*arr, sep = "")
```

Space Complexity of this approach would be `O(1).`

[forminator_quiz id="1273"]

This article tried to discuss Strings, Sorting. Hope this blog helps you understand and solve the problem. To practice more problems on Strings, Sorting you can check out MYCODE | Competitive Programming.