# Largest Number formed from an Array

Written by

## 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:

- We pass two elements for comparison to our function, say X and Y
- We have two possible numbers.
- X before Y(2 and 32 passed become 232)
- Y before X(2 and 32 become 322)

- We compare the two numbers and return the bigger number.
- 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) > 0 ? 1 : 0;`

}

void printLargest(vector<string> arr)

{

`sort(arr.begin(), arr.end(), compareFuncToSort); for (int i = 0; i < arr.size(); i++) cout << arr[i];`

}

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

`for (int i = 0; i < 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 << "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.