Recent Posts

Largest Number formed from an Array

Written by

Anshuman Raina

Largest Number formed from an Array Problem

PROBLEM: Find the largest number that can be generated from the numbers in an array.

Input: [32, 2, 4, 2, 24, 22]

Output: [432242222]

# Approach

The first solution that everyone thinks is to sort the array. But that solution will work in an array with elements of same number digits. Since here we have both 2 digit (32, 24,22) and 1 digit numbers, this won’t work here.

Eg. As we see in the final solution, 4 is placed at the front, which would not have been the result had we sorted the array.

Pseudo Code

We use the sort function present in the algorithm library, instead of replacing its default comparison function by our custom function compareFuncToSort, which will do as follows:

  1. We pass two elements for comparison to our function, say X and Y
  2. We have two possible numbers.
    1. X before Y(2 and 32 passed become 232)
    2. Y before X(2 and 32 become 322)
  3. We compare the two numbers and return the bigger number.
  4. This is the comparison function.

Simply calling the algorithm::sort with this function as an argument will give us the largest number.

Code:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int compareFuncToSort(string X, string Y)


{
string XY = X.append(Y);


string YX = Y.append(X);

return XY.compare(YX) &gt; 0 ? 1 : 0;



}


void printLargest(vector<string> arr)


{


sort(arr.begin(), arr.end(), compareFuncToSort);

for (int i = 0; i &lt; arr.size(); i++)

	cout &lt;&lt; arr[i];



}


void push(int arrInput[], int size)
{
vector<string> arr;


for (int i = 0; i &lt; size; i++)

{
	std::string s = std::to_string(arrInput[i]);
	arr.push_back(s);
}

printLargest(arr);



}


int main()
{


int arr[] = { 32, 2, 4, 2, 24, 22 };

cout &lt;&lt; "Largest number is ";

push(arr, 6);

return 0;



}

Output

Largest number is : 432242222

Time Complexity: O(N log N), where N is the number of elements

Space Complexity: O(1)

This is how we solve the problem of the Largest number from an array.

 

Largest Number formed from an Array