Largest Number Formed from an Array

Problem Statement

Given an array of N positive integers, arrange these integers in such a manner that when we join the elements, it is maximum among all possible permutations of the array elements.

(Basically: Find the Largest Number Formed From an Array)

Example

Input:

arr = [3, 30, 40, 9]

Output:

[9, 40, 3, 30]

Example Explanation

The given set of integers can be combined in the following ways:

• 330409
• 340309
• 403039
• 930340
• 933040
• 940330 ... and so on.

A total of 4!=24 permutations are possible. The task is to find the permutation which yields the maximum number.

Therefore for the given input, the largest number formed from the elements of the array is 940330. This is clearly explained using the below image:

Input

Input format during competitive programming consists of an array with N number of integers.

Output:

Output format includes printing the modified array which is in the format of the largest number formed from the elements of the array which is given as input.

Constraints

• 1 <= N (length of the array) <= $10^8$
• 1 <= arr[i] <= $10^4$

Approach 1

The first idea we get as soon we see this problem is using sorting. Let's assume we have the array consisting of elements [3, 9, 20, 640]. If we sort this set of integers in descending order we get [640, 20, 9, 3]. Now by combining these integers, we get a number 6402093, but the largest number formed from the elements of the given array is 9640320.

• Therefore, simple sorting doesn't give the largest number because 640 is greater than 9 but arranging them in descending order, doesn't yield the largest number formed from the array elements.
• So, this sorting technique should be modified a bit to obtain the largest number from the given set of elements. The modification includes sorting based on the comparison AB and BA as explained below.
• Assume the numbers taken are A and B, instead of comparing just values of A and B, compare by concatenating(combining) them as AB and BA.
• For example, if AB is greater than or equal to BA during the sorting process then we don't need to swap the values of A and B in the array.

Algorithm

Below is the algorithm which clearly explains the comparison-based sorting for forming the largest number from given array elements, which is a stable sorting technique because it does not swap the elements if they're of same value while comparing: For finding the largest number from the array of elements we need to do a little modification to the sorting technique which is discussed below. Consider two nested for loops with iterators i and j respectively.

• The first loop with iterator i starts from 0 to the length of the array.
• The second loop with iterator j starts from i to the length of the array.
  • For every two elements arr[i] and arr[j], convert them to strings. Let the strings be A and B, where A = string(arr[i]) and B = string(arr[j]).
  • Now combine them as AB and BA, and compare the values by converting them into an integer.
  • So, this simply means if int(AB)<int(BA), we need to swap the position of the numbers B and A in the array.
  • Else we don't need to swap these numbers.

At last return the modified array by swapping wherever it is needed.

Implementation

Below is the implementation of the largest number formed from the array elements using comparison sort in languages like C++, python, and java.

C++ implementation of the largest number using array elements by comparison sort which is we need to add comparator in the sorting algorithm for comparison based sorting:

Output:

Python implementation of the largest number formed from the array elements by comparison sort. This comparison sort is a modification of selection sort technique:

Output:

Java implementation of the largest number formed from the array elements by comparison sort:

Output:

Example Explanation:

The given set of integers can be combined in the following ways: 330409, 303409, 403039, 930340, 933040,.. and so on. There are many combinations present. Therefore for the given input, the largest number formed from the elements of the array is 940330.

Complexity Analysis

Time Complexity: $O(N^2)$, where N is the length of the array which is given as input.

• This $O(N^2)$ time complexity is taken for the comparison based sorting which is a basic modification of the selection sort technique.
• Comparison-based sorting is considered to have a time complexity of $O(N^2)$. Because we need to check for every element and compare it with all the elements on the right side and swap whenever the condition is satisfied.
• Swapping the elements is not a costly operation, because it has the time complexity $O(1)$.
• So the overall time complexity for finding the largest number formed from the given array elements using comparison sorting is $O(N^2)$.

Space Complexity: $O(1)$

• Constant space is required to perform in-place sorting in the algorithm mentioned above.

Approach 2: Only in Python

In python, we can use itertools to find the largest number formed from the given array of elements. The itertools is a module in python that provides us with a collection of functions to handle different iterators.

The itertools module in python is a fast, memory-efficient module that utilizes the system's computational resources efficiently. So, we use this module to find the largest number from the given array of elements for fast computation.

We can arrange these numbers in many ways and we get many different permutations by the arrangement of these array elements and we need to return the largest among all these permutations. In python we have class permutations which is present in the itertools module, so we import that for the simplification process and check for the largest among the formed permutations and return the largest number formed from the given array elements.

Algorithm

• The idea is to import permutations from itertools module.
• The second step includes storing all the permutations of these array elements.
• Each permutation of the array is converted to a string (representing the number) using the join() function.
• We need to return the largest number formed from all these permutations or strings. This can be done using the in-built max() function in python.

Implementation

Python implementation for finding the largest number from the given array elements using class permutations from the itertools module.

Output:

Example Explanation:

The given set of integers can be combined in the following ways: 330409, 303409, 403039, 930340, 933040,.. and so on. There are many combinations present. Therefore for the given input, the largest number formed from the elements of the array is 940330.

Complexity Analysis

Time Complexity: $O(N!)$, where N is the length of the array that is given as input.

• Each permutation of the input array is calculated in $O(1)$ time. Since N! number of permutations are possible, the overall time complexity of finding all permutations is $O(N!)$.
• And giving the maximum among this N! the number of permutations takes a time complexity of $O(N!)$. Therefore the overall time complexity is $O(N!)$$ for finding the largest number formed from all the array elements permutations.

Space Complexity: $O(N!)$, where N is the length of the array that is given as the input.

• $O(N!)$ space is needed to store all the permutations possible from the given input elements of the array and get the largest number from all those permutations.