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