Coderust: Hacking the Coding Interview/

...

/

Arrange the Largest Number

Arrange the Largest Number

Given an array of integers, find the arrangement that yields the largest number.

We'll cover the following...

Statement

Given an array of integers, find the largest number that can be made by creating all possible permutations of these integers.

As the largest number formed can be very large, Return a string instead of an integer.

Example

Let’s suppose an array with two numbers [3,21][3, 21].

We can only create two permutations with these two numbers and the largest number formed is 321321.

Sample input

[3, 30, 34, 5, 9]

Expected output

"9534330"

Try it yourself

#include <iostream>
#include <vector>
#include <string>
using namespace std;
string LargestNumber(const vector<int>& nums) {
  // TODO: WRITE - CODE - HERE
  return "";
}

Solution

To solve this problem, we need to apply some sorting technique. Since we need the largest number, we must ensure that the largest numbers occupy the most significant digits. We need to return a string as the created number can be very large. We start by converting all the elements of the array from integers to strings.

Now, we apply a sorting technique so we could create the largest number out of a sorted array. One may want to sort these numbers in descending order and then return the resultant string formed by this sorted array. But that is not always valid.

Let’s suppose we have the following array:

g array 71 5 21 52

If we sort the above array in descending order, we get the following array:

g array 71 52 21 5

The number formed by the simple concatenation of these strings is 71522157152215 whereas the largest number formed by rearranging these numbers is 71552217155221. This number is formed if our sorted array looks like the one below:

g array 71 5 52 21

During the sort, for each pairwise comparison, we compare the strings formed by concatenating the two strings in the pair in both orders. This enables the determination of the larger value of the two possible pairwise concatenations:

  • To prove that we can form a proper order by these comparisons, let’s assume that for two integers mm ...