Минимальная сумма 2 чисел, составленныхх из всех значений массива

Question

Дан массив цифр. Нужно составить из этих цифр два числа таких, что их сумма минимальна. На выход выдать эту сумму. Каждая цифра из массива должна использоваться ровно 1 раз.

Например, min_digits_sum([1,2,3]) = 12 + 3 = 15, а min_digits_sum([3,2,1,4,5,6,9,8,7,0]) = 16047

Попробовал составлять числа из наибольших и наименьших значений массива:

s_arr = sorted(arr)

if len(s_arr) % 2 == 0:
    ss1 = ''.join(map(str, s_arr[:(len(s_arr)//2):]))
    ss2 = ''.join(map(str, s_arr[(len(s_arr)//2)::]))
    s = int(ss1) + int(ss2)
else:
    ss1 = ''.join(map(str, s_arr[:(len(s_arr)//2)+1:]))
    ss2 = ''.join(map(str, s_arr[(len(s_arr)//2)+1::]))
    s = int(ss1) + int(ss2)


print(s)

Также думал о том, что самые большие цифры должны уходить в младшие разряды, но не знаю, верно ли это.

Подскажите с решением

Answer 1

Также думал о том, что самые большие цифры должны уходить в младшие разряды, но не знаю, верно ли это.

Да, это верно. Вы шли по правильному пути :)) Но тут можно обойтись без функций map, join и так далее.

Итак, вот ваш код:

s_arr = [3,2,1,4,5,6,9,8,7,0]
n = len(s_arr)
s_arr = sorted(s_arr)
num1 = num2 = 0
for i in range(n):
    if i % 2 == 0:
        num1 = num1 * 10 + s_arr[i]
    else:
        num2 = num2 * 10 + s_arr[i]
print(num1+num2)

Алгоритм:

приравниваем n к длине s_arr
сортируем s_arr по возрастанию
приравниваем num1 и num2 значение 0
повторить n раз:
- если шаг делится на 2:
  - num1 = num1 * 10 + s_arr[i]
- иначе:
  - num2 = num2 * 10 + s_arr[i]
печатаем сумму num и num2

Вывод:

Помог ли мой ответ?

Answer 2

Еще, как вариант:

s_arr = [3,2,1,4,5,6,9,8,7,0]
s = i = 0
arr = sorted(s_arr)
while arr:
    s += sum(arr[-2:])*10**i
    i += 1
    arr = arr[:-2]

print(s)  # 16047

код довольно простой, пояснять особо нечего: в цикле проходим по отсортированному списку, суммируем два последних элемента умножая сумму сначала на 1 потом на 10, затем на 100 и т.д., пока список не закончится.

БЛОГ НА HUSL

Минимальная сумма 2 чисел, составленныхх из всех значений массива

Ответы (2 шт):