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 0

return "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 permutations

from itertools import permutations

def 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 lst

print(largest([54, 546, 548, 60])) # Call largest function

Output

6054854654