Task 38. Максимально возможное число из массива
UniLecsЗадача: напишите функцию, которая принимает список не отрицательных целых чисел, упорядочивает их так, чтобы они составляли максимально возможное число.
Например, в массиве [ 819, 6, 89, 402, 4023, 54, 5 ] наибольшее сформированное число равно 8981965544024023.
Идея: на первый взгляд задача простая, нам нужно всего лишь "отсортировать по убыванию" и поставить большие цифры в начало.
Но необходимо как то учитывать степень числа. Например, т.к. 819 больше 89, то по нашему алгоритму мы должны число 819 поставить первым.
Но в таком случае мы получим не максимально возможное число: 8198940240236545 (контр-пример: 8981940240236545 > 8198940240236545).
Для того чтобы наш алгоритм с сортировкой работал, нам нужно каждое число довести до той же степени, что и наибольшее число в массиве.
Например,
массив из примера [ 819, 6, 89, 402, 4023, 54, 5 ] превратится в [ 819, 666, 899, 402, 4023, 544, 555 ]. Тогда после сортировки мы получим правильное расположение элементов для нахождения максимально возможного числа.
[ 819, 666, 899, 402, 4023 ] -> sort by descending -> [ 899, 819, 666, 555, 544, 402, 4023 ]
Дальше уже легко получить максимально возможное число: 8981965544024023
Реализация:
https://gist.github.com/unilecs/7e4b42682ef4c9e30df95192740fc70a
Тест: