question
Given an array of integers, devise an algorithm to find the largest number possible
from a concatenation of the integers in the array. Each number must be used exactly once.
ex. An input array:
returns: 4,321
order of #'s:
ex. 2:
returns: 5,958,521
order of #'s:
ex. 3:
returns: 976,655,756,560,555,545,405,054,512,010
order of #'s:
ex. An input array:
[1, 3, 2, 4]
returns: 4,321
order of #'s:
[4, 3, 2, 1]
ex. 2:
[59, 58, 5, 1, 2]
returns: 5,958,521
order of #'s:
[59, 58, 5, 2, 1]
ex. 3:
[54, 5, 55, 6, 7, 56, 120, 560, 540, 505, 9, 57, 0, 1, 45, 65]
returns: 976,655,756,560,555,545,405,054,512,010
order of #'s:
[9, 7, 6, 65, 57, 56, 560, 55, 5, 54, 540, 505, 45, 120, 1, 0]
Look into methods of lexicographical ordering.
But still remain skeptical of this method ;)
Unfortunately, using solely an lexicographical sorting algorithm will not return the correct answer.
ex.
A clever solution using your sorting algorithm of choice involves comparing the concatenation of two numbers with its reverse concatenation.
ex. From the previous example, when comparing 8 & 86, we can just compare 886 with 868. The first number of the bigger concatenation (in this case 8 because 886 > 868), should be considered the true larger number for our purposes.
In this method we avoid having to manually lexicographically compare numbers (which can become frustrating in boundary cases and the like. In conclusion, the solution can be attained by using any standard sorting algorithm and comparing the concatenations of any two numbers in the list as described above.
ex.
[8, 86, 89] sorted lexicographically (in decreasing order) would return [89, 86, 8].
But really, the correct ordering for our purposes is [89, 8, 86] (89886 vs 89868).
A clever solution using your sorting algorithm of choice involves comparing the concatenation of two numbers with its reverse concatenation.
ex. From the previous example, when comparing 8 & 86, we can just compare 886 with 868. The first number of the bigger concatenation (in this case 8 because 886 > 868), should be considered the true larger number for our purposes.
In this method we avoid having to manually lexicographically compare numbers (which can become frustrating in boundary cases and the like. In conclusion, the solution can be attained by using any standard sorting algorithm and comparing the concatenations of any two numbers in the list as described above.