# C++ Program to find the largest number formed from an array

Given an array, write a program to find the largest number that will be formed from the elements of the array. Arrangement should be done in such a way that all the elements contribute to make the largest number. Also, return the largest formed number in string format because the number can be very large.

For example

Test case 1

N = 5

Arr[] = {5, 9, 30, 3, 34}

Output = 9534330

Explanation

The largest value formed with the arrangement of 9,5,34,3,30.

Test case 2

N = 4

Arr[] = {60, 546, 548, 54}

Output = 6054854654

Explanation

The largest value formed with the arrangement of 60,548,546,54.

## Brute-force approach

A simple approach is to sort the array and form a string in order to make a largest number. The array sorted in descending order using bubble sort does not work here.

For example, if we take 548, it is greater than 60 but after sorting 60 comes before.

Similarly, 98 is greater than 9 but after sorting it comes after.

Below is the code implementation.

Code

`#include <algorithm>#include <iostream>#include <string>#include <vector>#include<bits/stdc++.h>using namespace std;string number(vector<int>& nums){ // declare a function  if( nums[0]==0 && nums[nums.size()-1] == 0) // if array contains 0return "0";        vector<string> result;          // push array element to string vector        for(auto x:nums){            result.push_back(to_string(x));        }          // Sort the result vector        for(int i=0;i<nums.size()-1;i++){            for(int j=0;j<nums.size()-i-1;j++){                if(result[j]+result[j+1]<result[j+1]+result[j]){                    swap(result[j],result[j+1]);                }            }        }          // Append it to ans string        string ans="";        for(int i=0;i<result.size();i++){            ans+=result[i];        }        return ans; // print ans}int main(){          vector<int> arr;          arr.push_back(54);          arr.push_back(546);          arr.push_back(548);          arr.push_back(60);cout  << number(arr);          return 0;}`

Output

`6054854654`

Time complexity

O(n*n)

Space complexity

O(1)

## Comparison based sorting

The problem occurred in the brute force approach will be covered in this approach. While sorting the array, we will modify the default compare function according to our needs.

The function my_compare() will work in this way.

This function will compare two numbers X and Y. If the formation of XY is greater then X will come first in the sorting order otherwise Y will come in the sorting order.

For example, if we have x as 541 and Y as 60. We compare 54160 and 60541. The greater one is 60541 so Y remains first.

Code

`#include <algorithm>#include <iostream>#include <string>#include <vector>#include<bits/stdc++.h>using namespace std;int my_Compare(int X, int Y){string x1= to_string(X); // x is  convert to string    string y1 =to_string(Y); // y is  convert to string                   string XY = x1.append(y1); // Make combination of XY by append X to Y          string YX = y1.append(x1); // Make combination of YX by append Y to X                return XY.compare(YX) > 0 ? 1 : 0; // Compare for the greater one}void printLargest(vector<int> arr){                 sort(arr.begin(), arr.end(), my_Compare); // Sort the arr by using my_Compare          for (int i = 0; i < arr.size(); i++)                   cout << arr[i]; // Print the array arranged in form of largest number}int main(){          vector<int> arr; // make a vector          arr.push_back(54);          arr.push_back(546);          arr.push_back(548);          arr.push_back(60);          printLargest(arr);         return 0;}`

Output

`6054854654`

Time complexity

O(nlogn)

Space complexity

O(n)

## Using itertools

If we want to do this problem using Python, a module itertools.combination() is used to find all the combinations of an array.

For example

Input : arr[] = [1, 2, 3, 4],

r = 2

Output : [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

Here r is the length of a set of sequences that can be formed.

Now this module can be applied to our array. We can find all the possible combinations of the array and make a string of a particular sequence set.

Finally, we will get the largest string.

Code

`#import itertools from permutationsfrom itertools import permutationsdef largest(l): # function to print largest number formed    lst = [] #an array to store the result    for i in permutations(l, len(l)):        # provides all permutations of the list values,        # store them in list to find max        lst.append("".join(map(str,i)))    return max(lst) # return max of the lstprint(largest([54, 546, 548, 60])) # Call largest function`

Output

`6054854654`